From e4ba6dbc3f1e76890b22773807ea37fe8fa2b1bc Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 10 Apr 2024 22:34:10 +0200 Subject: Adding upstream version 4.2.2. Signed-off-by: Daniel Baumann --- wsutil/wmem/wmem-int.h | 32 + wsutil/wmem/wmem.h | 43 + wsutil/wmem/wmem_allocator.h | 64 ++ wsutil/wmem/wmem_allocator_block.c | 1125 +++++++++++++++++++++++ wsutil/wmem/wmem_allocator_block.h | 46 + wsutil/wmem/wmem_allocator_block_fast.c | 261 ++++++ wsutil/wmem/wmem_allocator_block_fast.h | 41 + wsutil/wmem/wmem_allocator_simple.c | 152 ++++ wsutil/wmem/wmem_allocator_simple.h | 42 + wsutil/wmem/wmem_allocator_strict.c | 230 +++++ wsutil/wmem/wmem_allocator_strict.h | 45 + wsutil/wmem/wmem_array.c | 196 ++++ wsutil/wmem/wmem_array.h | 121 +++ wsutil/wmem/wmem_core.c | 240 +++++ wsutil/wmem/wmem_core.h | 252 ++++++ wsutil/wmem/wmem_interval_tree.c | 190 ++++ wsutil/wmem/wmem_interval_tree.h | 101 +++ wsutil/wmem/wmem_list.c | 276 ++++++ wsutil/wmem/wmem_list.h | 128 +++ wsutil/wmem/wmem_map.c | 515 +++++++++++ wsutil/wmem/wmem_map.h | 246 +++++ wsutil/wmem/wmem_map_int.h | 41 + wsutil/wmem/wmem_miscutl.c | 55 ++ wsutil/wmem/wmem_miscutl.h | 73 ++ wsutil/wmem/wmem_multimap.c | 185 ++++ wsutil/wmem/wmem_multimap.h | 195 ++++ wsutil/wmem/wmem_queue.h | 70 ++ wsutil/wmem/wmem_stack.c | 57 ++ wsutil/wmem/wmem_stack.h | 73 ++ wsutil/wmem/wmem_strbuf.c | 470 ++++++++++ wsutil/wmem/wmem_strbuf.h | 194 ++++ wsutil/wmem/wmem_strutl.c | 159 ++++ wsutil/wmem/wmem_strutl.h | 95 ++ wsutil/wmem/wmem_test.c | 1496 +++++++++++++++++++++++++++++++ wsutil/wmem/wmem_tree-int.h | 85 ++ wsutil/wmem/wmem_tree.c | 869 ++++++++++++++++++ wsutil/wmem/wmem_tree.h | 263 ++++++ wsutil/wmem/wmem_user_cb.c | 104 +++ wsutil/wmem/wmem_user_cb.h | 92 ++ wsutil/wmem/wmem_user_cb_int.h | 45 + 40 files changed, 8967 insertions(+) create mode 100644 wsutil/wmem/wmem-int.h create mode 100644 wsutil/wmem/wmem.h create mode 100644 wsutil/wmem/wmem_allocator.h create mode 100644 wsutil/wmem/wmem_allocator_block.c create mode 100644 wsutil/wmem/wmem_allocator_block.h create mode 100644 wsutil/wmem/wmem_allocator_block_fast.c create mode 100644 wsutil/wmem/wmem_allocator_block_fast.h create mode 100644 wsutil/wmem/wmem_allocator_simple.c create mode 100644 wsutil/wmem/wmem_allocator_simple.h create mode 100644 wsutil/wmem/wmem_allocator_strict.c create mode 100644 wsutil/wmem/wmem_allocator_strict.h create mode 100644 wsutil/wmem/wmem_array.c create mode 100644 wsutil/wmem/wmem_array.h create mode 100644 wsutil/wmem/wmem_core.c create mode 100644 wsutil/wmem/wmem_core.h create mode 100644 wsutil/wmem/wmem_interval_tree.c create mode 100644 wsutil/wmem/wmem_interval_tree.h create mode 100644 wsutil/wmem/wmem_list.c create mode 100644 wsutil/wmem/wmem_list.h create mode 100644 wsutil/wmem/wmem_map.c create mode 100644 wsutil/wmem/wmem_map.h create mode 100644 wsutil/wmem/wmem_map_int.h create mode 100644 wsutil/wmem/wmem_miscutl.c create mode 100644 wsutil/wmem/wmem_miscutl.h create mode 100644 wsutil/wmem/wmem_multimap.c create mode 100644 wsutil/wmem/wmem_multimap.h create mode 100644 wsutil/wmem/wmem_queue.h create mode 100644 wsutil/wmem/wmem_stack.c create mode 100644 wsutil/wmem/wmem_stack.h create mode 100644 wsutil/wmem/wmem_strbuf.c create mode 100644 wsutil/wmem/wmem_strbuf.h create mode 100644 wsutil/wmem/wmem_strutl.c create mode 100644 wsutil/wmem/wmem_strutl.h create mode 100644 wsutil/wmem/wmem_test.c create mode 100644 wsutil/wmem/wmem_tree-int.h create mode 100644 wsutil/wmem/wmem_tree.c create mode 100644 wsutil/wmem/wmem_tree.h create mode 100644 wsutil/wmem/wmem_user_cb.c create mode 100644 wsutil/wmem/wmem_user_cb.h create mode 100644 wsutil/wmem/wmem_user_cb_int.h (limited to 'wsutil/wmem') diff --git a/wsutil/wmem/wmem-int.h b/wsutil/wmem/wmem-int.h new file mode 100644 index 00000000..6c4e4985 --- /dev/null +++ b/wsutil/wmem/wmem-int.h @@ -0,0 +1,32 @@ +/** @file + * + * Internal definitions for the Wireshark Memory Manager + * Copyright 2012, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#ifndef __WMEM_INT_H__ +#define __WMEM_INT_H__ + +#include +#include + +#endif /* __WMEM_INT_H__ */ + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem.h b/wsutil/wmem/wmem.h new file mode 100644 index 00000000..81429151 --- /dev/null +++ b/wsutil/wmem/wmem.h @@ -0,0 +1,43 @@ +/** @file + * + * Definitions for the Wireshark Memory Manager + * Copyright 2012, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#ifndef __WMEM_H__ +#define __WMEM_H__ + +#include "wmem_array.h" +#include "wmem_core.h" +#include "wmem_list.h" +#include "wmem_map.h" +#include "wmem_miscutl.h" +#include "wmem_multimap.h" +#include "wmem_queue.h" +#include "wmem_stack.h" +#include "wmem_strbuf.h" +#include "wmem_strutl.h" +#include "wmem_tree.h" +#include "wmem_interval_tree.h" +#include "wmem_user_cb.h" + +#endif /* __WMEM_H__ */ + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_allocator.h b/wsutil/wmem/wmem_allocator.h new file mode 100644 index 00000000..8890054a --- /dev/null +++ b/wsutil/wmem/wmem_allocator.h @@ -0,0 +1,64 @@ +/** @file + * + * Definitions for the Wireshark Memory Manager Allocator + * Copyright 2012, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#ifndef __WMEM_ALLOCATOR_H__ +#define __WMEM_ALLOCATOR_H__ + +#include +#include + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +struct _wmem_user_cb_container_t; + +/* See section "4. Internal Design" of doc/README.wmem for details + * on this structure */ +struct _wmem_allocator_t { + /* Consumer functions */ + void *(*walloc)(void *private_data, const size_t size); + void (*wfree)(void *private_data, void *ptr); + void *(*wrealloc)(void *private_data, void *ptr, const size_t size); + + /* Producer/Manager functions */ + void (*free_all)(void *private_data); + void (*gc)(void *private_data); + void (*cleanup)(void *private_data); + + /* Callback List */ + struct _wmem_user_cb_container_t *callbacks; + + /* Implementation details */ + void *private_data; + enum _wmem_allocator_type_t type; + bool in_scope; +}; + +#ifdef __cplusplus +} +#endif /* __cplusplus */ + +#endif /* __WMEM_ALLOCATOR_H__ */ + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_allocator_block.c b/wsutil/wmem/wmem_allocator_block.c new file mode 100644 index 00000000..b8a0f598 --- /dev/null +++ b/wsutil/wmem/wmem_allocator_block.c @@ -0,0 +1,1125 @@ +/* wmem_allocator_block.c + * Wireshark Memory Manager Large-Block Allocator (version 3) + * Copyright 2013, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#include +#include + +#include + +#include "wmem_core.h" +#include "wmem_allocator.h" +#include "wmem_allocator_block.h" + +/* This has turned into a very interesting excercise in algorithms and data + * structures. + * + * HISTORY + * + * Version 1 of this allocator was embedded in the original emem framework. It + * didn't have to handle realloc or free, so it was very simple: it just grabbed + * a block from the OS and served allocations sequentially out of that until it + * ran out, then allocated a new block. The old block was never revisited, so + * it generally had a bit of wasted space at the end, but the waste was + * small enough that it was simply ignored. This allocator provided very fast + * constant-time allocation for any request that didn't require a new block from + * the OS, and that cost could be amortized away. + * + * Version 2 of this allocator was prompted by the need to support realloc and + * free in wmem. The original version simply didn't save enough metadata to do + * this, so I added a layer on top to make it possible. The primary principle + * was the same (allocate sequentially out of big blocks) with a bit of extra + * magic. Allocations were still fast constant-time, and frees were as well. + * Large parts of that design are still present in this one, but for more + * details see older versions of this file from git or svn. + * + * Version 3 of this allocator was written to address some issues that + * eventually showed up with version 2 under real-world usage. Specifically, + * version 2 dealt very poorly with memory fragmentation, almost never reusing + * freed blocks and choosing to just keep allocating from the master block + * instead. This led to particularly poor behaviour under the tick-tock loads + * (alloc/free/alloc/free or alloc/alloc/free/alloc/alloc/free/ or ...) that + * showed up in a couple of different protocol dissectors (TCP, Kafka). + * + * BLOCKS AND CHUNKS + * + * As in previous versions, allocations typically happen sequentially out of + * large OS-level blocks. Each block has a short embedded header used to + * maintain a doubly-linked list of all blocks (used or not) currently owned by + * the allocator. Each block is divided into chunks, which represent allocations + * and free sections (a block is initialized with one large, free, chunk). Each + * chunk is prefixed with a wmem_block_chunk_t structure, which is a short + * metadata header (8 bytes, regardless of 32 or 64-bit architecture unless + * alignment requires it to be padded) that contains the length of the chunk, + * the length of the previous chunk, a flag marking the chunk as free or used, + * and a flag marking the last chunk in a block. This serves to implement an + * inline sequential doubly-linked list of all the chunks in each block. A block + * with three chunks might look something like this: + * + * 0 _________________________ + * ^ ___________ / ______________ \ __________ + * ||---||--|-----/-----------||--------/--------------||--\-----/----------|| + * ||hdr|| prv | len | body || prv | len | body || prv | len | body || + * ||---||--------------------||--/--------------------||-------------------|| + * \______________________/ + * + * + * When allocating, a free chunk is found (more on that later) and split into + * two chunks: the first of the requested size and the second containing any + * remaining free. The first is marked used and returned to the caller. + * + * When freeing, the chunk in question is marked as free. Its neighbouring + * chunks are then checked; if either of them are free, the consecutive free + * chunks are merged into a single larger free chunk. Induction can show that + * applying this operation consistently prevents us ever having consecutive + * free chunks. + * + * Free chunks (because they are not being used for anything else) each store an + * additional pair of pointers (see the wmem_block_free_t structure) that form + * the backbone of the data structures used to track free chunks. + * + * MASTER AND RECYCLER + * + * The extra pair of pointers in free chunks are used to build two doubly-linked + * lists: the master and the recycler. The recycler is circular, the master is + * a stack. + * + * The master stack is only populated by chunks from new OS-level blocks, + * so every chunk in this list is guaranteed to be able to serve any allocation + * request (the allocator will not serve requests larger than its block size). + * The chunk at the head of the master list shrinks as it serves requests. When + * it is too small to serve the current request, it is popped and inserted into + * the recycler. If the master list is empty, a new OS-level block is allocated, + * and its chunk is pushed onto the master stack. + * + * The recycler is populated by 'leftovers' from the master, as well as any + * chunks that were returned to the allocator via a call to free(). Although the + * recycler is circular, we will refer to the element referenced from the + * allocator as the 'head' of the list for convenience. The primary operation on + * the recycler is called cycling it. In this operation, the head is compared + * with its clockwise neighbour. If the neighbour is as large or larger, it + * becomes the head (the list rotates counter-clockwise). If the neighbour is + * smaller, then it is removed from its location and inserted as the counter- + * clockwise neighbour of the head (the list still rotates counter-clockwise, + * but the head element is held fixed while the rest of the list spins). This + * operation has the following properties: + * - fast constant time + * - once the largest chunk is at the head, it remains at the head + * - more iterations increases the probability that the largest chunk will be + * the head (for a list with n items, n iterations guarantees that the + * largest chunk will be the head). + * + * ALLOCATING + * + * When an allocation request is received, the allocator first attempts to + * satisfy it with the chunk at the head of the recycler. If that does not + * succeed, the request is satisfied by the master list instead. Regardless of + * which chunk satisfied the request, the recycler is always cycled. + */ + +/* https://mail.gnome.org/archives/gtk-devel-list/2004-December/msg00091.html + * The 2*sizeof(size_t) alignment here is borrowed from GNU libc, so it should + * be good most everywhere. It is more conservative than is needed on some + * 64-bit platforms, but ia64 does require a 16-byte alignment. The SIMD + * extensions for x86 and ppc32 would want a larger alignment than this, but + * we don't need to do better than malloc. + */ +#define WMEM_ALIGN_AMOUNT (2 * sizeof (size_t)) +#define WMEM_ALIGN_SIZE(SIZE) ((~(WMEM_ALIGN_AMOUNT-1)) & \ + ((SIZE) + (WMEM_ALIGN_AMOUNT-1))) + +/* When required, allocate more memory from the OS in chunks of this size. + * 8MB is a pretty arbitrary value - it's big enough that it should last a while + * and small enough that a mostly-unused one doesn't waste *too* much. It's + * also a nice power of two, of course. */ +#define WMEM_BLOCK_SIZE (8 * 1024 * 1024) + +/* The header for an entire OS-level 'block' of memory */ +typedef struct _wmem_block_hdr_t { + struct _wmem_block_hdr_t *prev, *next; +} wmem_block_hdr_t; + +/* The header for a single 'chunk' of memory as returned from alloc/realloc. + * The 'jumbo' flag indicates an allocation larger than a normal-sized block + * would be capable of serving. If this is set, it is the only chunk in the + * block and the other chunk header fields are irrelevant. + */ +typedef struct _wmem_block_chunk_t { + uint32_t prev; + + /* flags */ + uint32_t last:1; + uint32_t used:1; + uint32_t jumbo:1; + + uint32_t len:29; +} wmem_block_chunk_t; + +/* Handy macros for navigating the chunks in a block as if they were a + * doubly-linked list. */ +#define WMEM_CHUNK_PREV(CHUNK) ((CHUNK)->prev \ + ? ((wmem_block_chunk_t*)(((uint8_t*)(CHUNK)) - (CHUNK)->prev)) \ + : NULL) + +#define WMEM_CHUNK_NEXT(CHUNK) ((CHUNK)->last \ + ? NULL \ + : ((wmem_block_chunk_t*)(((uint8_t*)(CHUNK)) + (CHUNK)->len))) + +#define WMEM_CHUNK_HEADER_SIZE WMEM_ALIGN_SIZE(sizeof(wmem_block_chunk_t)) + +#define WMEM_BLOCK_MAX_ALLOC_SIZE (WMEM_BLOCK_SIZE - \ + (WMEM_BLOCK_HEADER_SIZE + WMEM_CHUNK_HEADER_SIZE)) + +/* other handy chunk macros */ +#define WMEM_CHUNK_TO_DATA(CHUNK) ((void*)((uint8_t*)(CHUNK) + WMEM_CHUNK_HEADER_SIZE)) +#define WMEM_DATA_TO_CHUNK(DATA) ((wmem_block_chunk_t*)((uint8_t*)(DATA) - WMEM_CHUNK_HEADER_SIZE)) +#define WMEM_CHUNK_DATA_LEN(CHUNK) ((CHUNK)->len - WMEM_CHUNK_HEADER_SIZE) + +/* some handy block macros */ +#define WMEM_BLOCK_HEADER_SIZE WMEM_ALIGN_SIZE(sizeof(wmem_block_hdr_t)) +#define WMEM_BLOCK_TO_CHUNK(BLOCK) ((wmem_block_chunk_t*)((uint8_t*)(BLOCK) + WMEM_BLOCK_HEADER_SIZE)) +#define WMEM_CHUNK_TO_BLOCK(CHUNK) ((wmem_block_hdr_t*)((uint8_t*)(CHUNK) - WMEM_BLOCK_HEADER_SIZE)) + +/* This is what the 'data' section of a chunk contains if it is free. */ +typedef struct _wmem_block_free_t { + wmem_block_chunk_t *prev, *next; +} wmem_block_free_t; + +/* Handy macro for accessing the free-header of a chunk */ +#define WMEM_GET_FREE(CHUNK) ((wmem_block_free_t*)WMEM_CHUNK_TO_DATA(CHUNK)) + +typedef struct _wmem_block_allocator_t { + wmem_block_hdr_t *block_list; + wmem_block_chunk_t *master_head; + wmem_block_chunk_t *recycler_head; +} wmem_block_allocator_t; + +/* DEBUG AND TEST */ +static int +wmem_block_verify_block(wmem_block_hdr_t *block) +{ + int total_free_space = 0; + uint32_t total_len; + wmem_block_chunk_t *chunk; + + chunk = WMEM_BLOCK_TO_CHUNK(block); + total_len = WMEM_BLOCK_HEADER_SIZE; + + if (chunk->jumbo) { + /* We can tell nothing else about jumbo chunks except that they are + * always used. */ + return 0; + } + + g_assert_true(chunk->prev == 0); + + do { + total_len += chunk->len; + + g_assert_true(chunk->len >= WMEM_CHUNK_HEADER_SIZE); + g_assert_true(!chunk->jumbo); + + if (WMEM_CHUNK_NEXT(chunk)) { + g_assert_true(chunk->len == WMEM_CHUNK_NEXT(chunk)->prev); + } + + if (!chunk->used && + WMEM_CHUNK_DATA_LEN(chunk) >= sizeof(wmem_block_free_t)) { + + total_free_space += chunk->len; + + if (!chunk->last) { + g_assert_true(WMEM_GET_FREE(chunk)->next); + g_assert_true(WMEM_GET_FREE(chunk)->prev); + } + } + + chunk = WMEM_CHUNK_NEXT(chunk); + } while (chunk); + + g_assert_true(total_len == WMEM_BLOCK_SIZE); + + return total_free_space; +} + +static int +wmem_block_verify_master_list(wmem_block_allocator_t *allocator) +{ + wmem_block_chunk_t *cur; + wmem_block_free_t *cur_free; + int free_space = 0; + + cur = allocator->master_head; + if (!cur) { + return 0; + } + + g_assert_true(WMEM_GET_FREE(cur)->prev == NULL); + + while (cur) { + free_space += cur->len; + + cur_free = WMEM_GET_FREE(cur); + + g_assert_true(! cur->used); + + if (cur_free->next) { + g_assert_true(WMEM_GET_FREE(cur_free->next)->prev == cur); + } + + if (cur != allocator->master_head) { + g_assert_true(cur->len == WMEM_BLOCK_SIZE); + } + + cur = cur_free->next; + } + + return free_space; +} + +static int +wmem_block_verify_recycler(wmem_block_allocator_t *allocator) +{ + wmem_block_chunk_t *cur; + wmem_block_free_t *cur_free; + int free_space = 0; + + cur = allocator->recycler_head; + if (!cur) { + return 0; + } + + do { + free_space += cur->len; + + cur_free = WMEM_GET_FREE(cur); + + g_assert_true(! cur->used); + + g_assert_true(cur_free->prev); + g_assert_true(cur_free->next); + + g_assert_true(WMEM_GET_FREE(cur_free->prev)->next == cur); + g_assert_true(WMEM_GET_FREE(cur_free->next)->prev == cur); + + cur = cur_free->next; + } while (cur != allocator->recycler_head); + + return free_space; +} + +void +wmem_block_verify(wmem_allocator_t *allocator) +{ + wmem_block_hdr_t *cur; + wmem_block_allocator_t *private_allocator; + int master_free, recycler_free, chunk_free = 0; + + /* Normally it would be bad for an allocator helper function to depend + * on receiving the right type of allocator, but this is for testing only + * and is not part of any real API. */ + g_assert_true(allocator->type == WMEM_ALLOCATOR_BLOCK); + + private_allocator = (wmem_block_allocator_t*) allocator->private_data; + + if (private_allocator->block_list == NULL) { + g_assert_true(! private_allocator->master_head); + g_assert_true(! private_allocator->recycler_head); + return; + } + + master_free = wmem_block_verify_master_list(private_allocator); + recycler_free = wmem_block_verify_recycler(private_allocator); + + cur = private_allocator->block_list; + g_assert_true(cur->prev == NULL); + while (cur) { + if (cur->next) { + g_assert_true(cur->next->prev == cur); + } + chunk_free += wmem_block_verify_block(cur); + cur = cur->next; + } + + g_assert_true(chunk_free == master_free + recycler_free); +} + +/* MASTER/RECYCLER HELPERS */ + +/* Cycles the recycler. See the design notes at the top of this file for more + * details. */ +static void +wmem_block_cycle_recycler(wmem_block_allocator_t *allocator) +{ + wmem_block_chunk_t *chunk; + wmem_block_free_t *free_chunk; + + chunk = allocator->recycler_head; + + if (chunk == NULL) { + return; + } + + free_chunk = WMEM_GET_FREE(chunk); + + if (free_chunk->next->len < chunk->len) { + /* Hold the current head fixed during rotation. */ + WMEM_GET_FREE(free_chunk->next)->prev = free_chunk->prev; + WMEM_GET_FREE(free_chunk->prev)->next = free_chunk->next; + + free_chunk->prev = free_chunk->next; + free_chunk->next = WMEM_GET_FREE(free_chunk->next)->next; + + WMEM_GET_FREE(free_chunk->next)->prev = chunk; + WMEM_GET_FREE(free_chunk->prev)->next = chunk; + } + else { + /* Just rotate everything. */ + allocator->recycler_head = free_chunk->next; + } +} + +/* Adds a chunk from the recycler. */ +static void +wmem_block_add_to_recycler(wmem_block_allocator_t *allocator, + wmem_block_chunk_t *chunk) +{ + wmem_block_free_t *free_chunk; + + if (WMEM_CHUNK_DATA_LEN(chunk) < sizeof(wmem_block_free_t)) { + return; + } + + free_chunk = WMEM_GET_FREE(chunk); + + if (! allocator->recycler_head) { + /* First one */ + free_chunk->next = chunk; + free_chunk->prev = chunk; + allocator->recycler_head = chunk; + } + else { + free_chunk->next = allocator->recycler_head; + free_chunk->prev = WMEM_GET_FREE(allocator->recycler_head)->prev; + + WMEM_GET_FREE(free_chunk->next)->prev = chunk; + WMEM_GET_FREE(free_chunk->prev)->next = chunk; + + if (chunk->len > allocator->recycler_head->len) { + allocator->recycler_head = chunk; + } + } +} + +/* Removes a chunk from the recycler. */ +static void +wmem_block_remove_from_recycler(wmem_block_allocator_t *allocator, + wmem_block_chunk_t *chunk) +{ + wmem_block_free_t *free_chunk; + + free_chunk = WMEM_GET_FREE(chunk); + + if (free_chunk->prev == chunk && free_chunk->next == chunk) { + /* Only one item in recycler, just empty it. */ + allocator->recycler_head = NULL; + } + else { + /* Two or more items, usual doubly-linked-list removal. It's circular + * so we don't need to worry about null-checking anything, which is + * nice. */ + WMEM_GET_FREE(free_chunk->prev)->next = free_chunk->next; + WMEM_GET_FREE(free_chunk->next)->prev = free_chunk->prev; + if (allocator->recycler_head == chunk) { + allocator->recycler_head = free_chunk->next; + } + } +} + +/* Pushes a chunk onto the master stack. */ +static void +wmem_block_push_master(wmem_block_allocator_t *allocator, + wmem_block_chunk_t *chunk) +{ + wmem_block_free_t *free_chunk; + + free_chunk = WMEM_GET_FREE(chunk); + free_chunk->prev = NULL; + free_chunk->next = allocator->master_head; + if (free_chunk->next) { + WMEM_GET_FREE(free_chunk->next)->prev = chunk; + } + allocator->master_head = chunk; +} + +/* Removes the top chunk from the master stack. */ +static void +wmem_block_pop_master(wmem_block_allocator_t *allocator) +{ + wmem_block_chunk_t *chunk; + wmem_block_free_t *free_chunk; + + chunk = allocator->master_head; + + free_chunk = WMEM_GET_FREE(chunk); + + allocator->master_head = free_chunk->next; + if (free_chunk->next) { + WMEM_GET_FREE(free_chunk->next)->prev = NULL; + } +} + +/* CHUNK HELPERS */ + +/* Takes a free chunk and checks the chunks to its immediate right and left in + * the block. If they are also free, the contigous free chunks are merged into + * a single free chunk. The resulting chunk ends up in either the master list or + * the recycler, depending on where the merged chunks were originally. + */ +static void +wmem_block_merge_free(wmem_block_allocator_t *allocator, + wmem_block_chunk_t *chunk) +{ + wmem_block_chunk_t *tmp; + wmem_block_chunk_t *left_free = NULL; + wmem_block_chunk_t *right_free = NULL; + + /* Check the chunk to our right. If it is free, merge it into our current + * chunk. If it is big enough to hold a free-header, save it for later (we + * need to know about the left chunk before we decide what goes where). */ + tmp = WMEM_CHUNK_NEXT(chunk); + if (tmp && !tmp->used) { + if (WMEM_CHUNK_DATA_LEN(tmp) >= sizeof(wmem_block_free_t)) { + right_free = tmp; + } + chunk->len += tmp->len; + chunk->last = tmp->last; + } + + /* Check the chunk to our left. If it is free, merge our current chunk into + * it (thus chunk = tmp). As before, save it if it has enough space to + * hold a free-header. */ + tmp = WMEM_CHUNK_PREV(chunk); + if (tmp && !tmp->used) { + if (WMEM_CHUNK_DATA_LEN(tmp) >= sizeof(wmem_block_free_t)) { + left_free = tmp; + } + tmp->len += chunk->len; + tmp->last = chunk->last; + chunk = tmp; + } + + /* The length of our chunk may have changed. If we have a chunk following, + * update its 'prev' count. */ + if (!chunk->last) { + WMEM_CHUNK_NEXT(chunk)->prev = chunk->len; + } + + /* Now that the chunk headers are merged and consistent, we need to figure + * out what goes where in which free list. */ + if (right_free && right_free == allocator->master_head) { + /* If we merged right, and that chunk was the head of the master list, + * then we leave the resulting chunk at the head of the master list. */ + wmem_block_free_t *moved; + if (left_free) { + wmem_block_remove_from_recycler(allocator, left_free); + } + moved = WMEM_GET_FREE(chunk); + moved->prev = NULL; + moved->next = WMEM_GET_FREE(right_free)->next; + allocator->master_head = chunk; + if (moved->next) { + WMEM_GET_FREE(moved->next)->prev = chunk; + } + } + else { + /* Otherwise, we remove the right-merged chunk (if there was one) from + * the recycler. Then, if we merged left we have nothing to do, since + * that recycler entry is still valid. If not, we add the chunk. */ + if (right_free) { + wmem_block_remove_from_recycler(allocator, right_free); + } + if (!left_free) { + wmem_block_add_to_recycler(allocator, chunk); + } + } +} + +/* Takes an unused chunk and a size, and splits it into two chunks if possible. + * The first chunk (at the same address as the input chunk) is guaranteed to + * hold at least `size` bytes of data, and to not be in either the master or + * recycler lists. + * + * The second chunk gets whatever data is left over. It is marked unused and + * replaces the input chunk in whichever list it originally inhabited. */ +static void +wmem_block_split_free_chunk(wmem_block_allocator_t *allocator, + wmem_block_chunk_t *chunk, + const size_t size) +{ + wmem_block_chunk_t *extra; + wmem_block_free_t *old_blk, *new_blk; + size_t aligned_size, available; + bool last; + + aligned_size = WMEM_ALIGN_SIZE(size) + WMEM_CHUNK_HEADER_SIZE; + + if (WMEM_CHUNK_DATA_LEN(chunk) < aligned_size + sizeof(wmem_block_free_t)) { + /* If the available space is not enought to store all of + * (hdr + requested size + alignment padding + hdr + free-header) then + * just remove the current chunk from the free list and return, since we + * can't usefully split it. */ + if (chunk == allocator->master_head) { + wmem_block_pop_master(allocator); + } + else if (WMEM_CHUNK_DATA_LEN(chunk) >= sizeof(wmem_block_free_t)) { + wmem_block_remove_from_recycler(allocator, chunk); + } + return; + } + + /* preserve a few values from chunk that we'll need to manipulate */ + last = chunk->last; + available = chunk->len - aligned_size; + + /* set new values for chunk */ + chunk->len = (uint32_t) aligned_size; + chunk->last = false; + + /* with chunk's values set, we can use the standard macro to calculate + * the location and size of the new free chunk */ + extra = WMEM_CHUNK_NEXT(chunk); + + /* Now we move the free chunk's address without changing its location + * in whichever list it is in. + * + * Note that the new chunk header 'extra' may overlap the old free header, + * so we have to copy the free header before we write anything to extra. + */ + old_blk = WMEM_GET_FREE(chunk); + new_blk = WMEM_GET_FREE(extra); + + if (allocator->master_head == chunk) { + new_blk->prev = old_blk->prev; + new_blk->next = old_blk->next; + + if (old_blk->next) { + WMEM_GET_FREE(old_blk->next)->prev = extra; + } + + allocator->master_head = extra; + } + else { + if (old_blk->prev == chunk) { + new_blk->prev = extra; + new_blk->next = extra; + } + else { + new_blk->prev = old_blk->prev; + new_blk->next = old_blk->next; + + WMEM_GET_FREE(old_blk->prev)->next = extra; + WMEM_GET_FREE(old_blk->next)->prev = extra; + } + + if (allocator->recycler_head == chunk) { + allocator->recycler_head = extra; + } + } + + /* Now that we've copied over the free-list stuff (which may have overlapped + * with our new chunk header) we can safely write our new chunk header. */ + extra->len = (uint32_t) available; + extra->last = last; + extra->prev = chunk->len; + extra->used = false; + extra->jumbo = false; + + /* Correctly update the following chunk's back-pointer */ + if (!last) { + WMEM_CHUNK_NEXT(extra)->prev = extra->len; + } +} + +/* Takes a used chunk and a size, and splits it into two chunks if possible. + * The first chunk can hold at least `size` bytes of data, while the second gets + * whatever's left over. The second is marked as unused and is added to the + * recycler. */ +static void +wmem_block_split_used_chunk(wmem_block_allocator_t *allocator, + wmem_block_chunk_t *chunk, + const size_t size) +{ + wmem_block_chunk_t *extra; + size_t aligned_size, available; + bool last; + + aligned_size = WMEM_ALIGN_SIZE(size) + WMEM_CHUNK_HEADER_SIZE; + + if (aligned_size > WMEM_CHUNK_DATA_LEN(chunk)) { + /* in this case we don't have enough space to really split it, so + * it's basically a no-op */ + return; + } + /* otherwise, we have room to split it, though the remaining free chunk + * may still not be usefully large */ + + /* preserve a few values from chunk that we'll need to manipulate */ + last = chunk->last; + available = chunk->len - aligned_size; + + /* set new values for chunk */ + chunk->len = (uint32_t) aligned_size; + chunk->last = false; + + /* with chunk's values set, we can use the standard macro to calculate + * the location and size of the new free chunk */ + extra = WMEM_CHUNK_NEXT(chunk); + + /* set the new values for the chunk */ + extra->len = (uint32_t) available; + extra->last = last; + extra->prev = chunk->len; + extra->used = false; + extra->jumbo = false; + + /* Correctly update the following chunk's back-pointer */ + if (!last) { + WMEM_CHUNK_NEXT(extra)->prev = extra->len; + } + + /* Merge it to its right if possible (it can't be merged left, obviously). + * This also adds it to the recycler. */ + wmem_block_merge_free(allocator, extra); +} + +/* BLOCK HELPERS */ + +/* Add a block to the allocator's embedded doubly-linked list of OS-level blocks + * that it owns. */ +static void +wmem_block_add_to_block_list(wmem_block_allocator_t *allocator, + wmem_block_hdr_t *block) +{ + block->prev = NULL; + block->next = allocator->block_list; + if (block->next) { + block->next->prev = block; + } + allocator->block_list = block; +} + +/* Remove a block from the allocator's embedded doubly-linked list of OS-level + * blocks that it owns. */ +static void +wmem_block_remove_from_block_list(wmem_block_allocator_t *allocator, + wmem_block_hdr_t *block) +{ + if (block->prev) { + block->prev->next = block->next; + } + else { + allocator->block_list = block->next; + } + + if (block->next) { + block->next->prev = block->prev; + } +} + +/* Initializes a single unused chunk at the beginning of the block, and + * adds that chunk to the free list. */ +static void +wmem_block_init_block(wmem_block_allocator_t *allocator, + wmem_block_hdr_t *block) +{ + wmem_block_chunk_t *chunk; + + /* a new block contains one chunk, right at the beginning */ + chunk = WMEM_BLOCK_TO_CHUNK(block); + + chunk->used = false; + chunk->jumbo = false; + chunk->last = true; + chunk->prev = 0; + chunk->len = WMEM_BLOCK_SIZE - WMEM_BLOCK_HEADER_SIZE; + + /* now push that chunk onto the master list */ + wmem_block_push_master(allocator, chunk); +} + +/* Creates a new block, and initializes it. */ +static void +wmem_block_new_block(wmem_block_allocator_t *allocator) +{ + wmem_block_hdr_t *block; + + /* allocate the new block and add it to the block list */ + block = (wmem_block_hdr_t *)wmem_alloc(NULL, WMEM_BLOCK_SIZE); + wmem_block_add_to_block_list(allocator, block); + + /* initialize it */ + wmem_block_init_block(allocator, block); +} + +/* JUMBO ALLOCATIONS */ + +/* Allocates special 'jumbo' blocks for sizes that won't fit normally. */ +static void * +wmem_block_alloc_jumbo(wmem_block_allocator_t *allocator, const size_t size) +{ + wmem_block_hdr_t *block; + wmem_block_chunk_t *chunk; + + /* allocate a new block of exactly the right size */ + block = (wmem_block_hdr_t *) wmem_alloc(NULL, size + + WMEM_BLOCK_HEADER_SIZE + + WMEM_CHUNK_HEADER_SIZE); + + /* add it to the block list */ + wmem_block_add_to_block_list(allocator, block); + + /* the new block contains a single jumbo chunk */ + chunk = WMEM_BLOCK_TO_CHUNK(block); + chunk->last = true; + chunk->used = true; + chunk->jumbo = true; + chunk->len = 0; + chunk->prev = 0; + + /* and return the data pointer */ + return WMEM_CHUNK_TO_DATA(chunk); +} + +/* Frees special 'jumbo' blocks of sizes that won't fit normally. */ +static void +wmem_block_free_jumbo(wmem_block_allocator_t *allocator, + wmem_block_chunk_t *chunk) +{ + wmem_block_hdr_t *block; + + block = WMEM_CHUNK_TO_BLOCK(chunk); + + wmem_block_remove_from_block_list(allocator, block); + + wmem_free(NULL, block); +} + +/* Reallocs special 'jumbo' blocks of sizes that won't fit normally. */ +static void * +wmem_block_realloc_jumbo(wmem_block_allocator_t *allocator, + wmem_block_chunk_t *chunk, + const size_t size) +{ + wmem_block_hdr_t *block; + + block = WMEM_CHUNK_TO_BLOCK(chunk); + + block = (wmem_block_hdr_t *) wmem_realloc(NULL, block, size + + WMEM_BLOCK_HEADER_SIZE + + WMEM_CHUNK_HEADER_SIZE); + + if (block->next) { + block->next->prev = block; + } + + if (block->prev) { + block->prev->next = block; + } + else { + allocator->block_list = block; + } + + return WMEM_CHUNK_TO_DATA(WMEM_BLOCK_TO_CHUNK(block)); +} + +/* API */ + +static void * +wmem_block_alloc(void *private_data, const size_t size) +{ + wmem_block_allocator_t *allocator = (wmem_block_allocator_t*) private_data; + wmem_block_chunk_t *chunk; + + if (size > WMEM_BLOCK_MAX_ALLOC_SIZE) { + return wmem_block_alloc_jumbo(allocator, size); + } + + if (allocator->recycler_head && + WMEM_CHUNK_DATA_LEN(allocator->recycler_head) >= size) { + + /* If we can serve it from the recycler, do so. */ + chunk = allocator->recycler_head; + } + else { + if (allocator->master_head && + WMEM_CHUNK_DATA_LEN(allocator->master_head) < size) { + + /* Recycle the head of the master list if necessary. */ + chunk = allocator->master_head; + wmem_block_pop_master(allocator); + wmem_block_add_to_recycler(allocator, chunk); + } + + if (!allocator->master_head) { + /* Allocate a new block if necessary. */ + wmem_block_new_block(allocator); + } + + chunk = allocator->master_head; + } + + /* Split our chunk into two to preserve any trailing free space */ + wmem_block_split_free_chunk(allocator, chunk, size); + + /* Now cycle the recycler */ + wmem_block_cycle_recycler(allocator); + + /* mark it as used */ + chunk->used = true; + + /* and return the user's pointer */ + return WMEM_CHUNK_TO_DATA(chunk); +} + +static void +wmem_block_free(void *private_data, void *ptr) +{ + wmem_block_allocator_t *allocator = (wmem_block_allocator_t*) private_data; + wmem_block_chunk_t *chunk; + + chunk = WMEM_DATA_TO_CHUNK(ptr); + + if (chunk->jumbo) { + wmem_block_free_jumbo(allocator, chunk); + return; + } + + /* mark it as unused */ + chunk->used = false; + + /* merge it with any other free chunks adjacent to it, so that contiguous + * free space doesn't get fragmented */ + wmem_block_merge_free(allocator, chunk); + + /* Now cycle the recycler */ + wmem_block_cycle_recycler(allocator); +} + +static void * +wmem_block_realloc(void *private_data, void *ptr, const size_t size) +{ + wmem_block_allocator_t *allocator = (wmem_block_allocator_t*) private_data; + wmem_block_chunk_t *chunk; + + chunk = WMEM_DATA_TO_CHUNK(ptr); + + if (chunk->jumbo) { + return wmem_block_realloc_jumbo(allocator, chunk, size); + } + + if (size > WMEM_CHUNK_DATA_LEN(chunk)) { + /* grow */ + wmem_block_chunk_t *tmp; + + tmp = WMEM_CHUNK_NEXT(chunk); + + if (tmp && (!tmp->used) && + (size < WMEM_CHUNK_DATA_LEN(chunk) + tmp->len)) { + /* the next chunk is free and has enough extra, so just grab + * from that */ + size_t split_size; + + /* we ask for the next chunk to be split, but we don't end up + * using the split chunk header (it just gets merged into this one), + * so we want the split to be of (size - curdatalen - header_size). + * However, this can underflow by header_size, so we do a quick + * check here and floor the value to 0. */ + split_size = size - WMEM_CHUNK_DATA_LEN(chunk); + + if (split_size < WMEM_CHUNK_HEADER_SIZE) { + split_size = 0; + } + else { + split_size -= WMEM_CHUNK_HEADER_SIZE; + } + + wmem_block_split_free_chunk(allocator, tmp, split_size); + + /* Now do a 'quickie' merge between the current block and the left- + * hand side of the split. Simply calling wmem_block_merge_free + * might confuse things, since we may temporarily have two blocks + * to our right that are both free (and it isn't guaranteed to + * handle that case). Update our 'next' count and last flag, and + * our (new) successor's 'prev' count */ + chunk->len += tmp->len; + chunk->last = tmp->last; + tmp = WMEM_CHUNK_NEXT(chunk); + if (tmp) { + tmp->prev = chunk->len; + } + + /* Now cycle the recycler */ + wmem_block_cycle_recycler(allocator); + + /* And return the same old pointer */ + return ptr; + } + else { + /* no room to grow, need to alloc, copy, free */ + void *newptr; + + newptr = wmem_block_alloc(private_data, size); + memcpy(newptr, ptr, WMEM_CHUNK_DATA_LEN(chunk)); + wmem_block_free(private_data, ptr); + + /* No need to cycle the recycler, alloc and free both did that + * already */ + + return newptr; + } + } + else if (size < WMEM_CHUNK_DATA_LEN(chunk)) { + /* shrink */ + wmem_block_split_used_chunk(allocator, chunk, size); + + /* Now cycle the recycler */ + wmem_block_cycle_recycler(allocator); + + return ptr; + } + + /* no-op */ + return ptr; +} + +static void +wmem_block_free_all(void *private_data) +{ + wmem_block_allocator_t *allocator = (wmem_block_allocator_t*) private_data; + wmem_block_hdr_t *cur; + wmem_block_chunk_t *chunk; + + /* the existing free lists are entirely irrelevant */ + allocator->master_head = NULL; + allocator->recycler_head = NULL; + + /* iterate through the blocks, reinitializing each one */ + cur = allocator->block_list; + + while (cur) { + chunk = WMEM_BLOCK_TO_CHUNK(cur); + if (chunk->jumbo) { + wmem_block_remove_from_block_list(allocator, cur); + cur = cur->next; + wmem_free(NULL, WMEM_CHUNK_TO_BLOCK(chunk)); + } + else { + wmem_block_init_block(allocator, cur); + cur = cur->next; + } + } +} + +static void +wmem_block_gc(void *private_data) +{ + wmem_block_allocator_t *allocator = (wmem_block_allocator_t*) private_data; + wmem_block_hdr_t *cur, *next; + wmem_block_chunk_t *chunk; + wmem_block_free_t *free_chunk; + + /* Walk through the blocks, adding used blocks to the new list and + * completely destroying unused blocks. */ + cur = allocator->block_list; + allocator->block_list = NULL; + + while (cur) { + chunk = WMEM_BLOCK_TO_CHUNK(cur); + next = cur->next; + + if (!chunk->jumbo && !chunk->used && chunk->last) { + /* If the first chunk is also the last, and is unused, then + * the block as a whole is entirely unused, so return it to + * the OS and remove it from whatever lists it is in. */ + free_chunk = WMEM_GET_FREE(chunk); + if (free_chunk->next) { + WMEM_GET_FREE(free_chunk->next)->prev = free_chunk->prev; + } + if (free_chunk->prev) { + WMEM_GET_FREE(free_chunk->prev)->next = free_chunk->next; + } + if (allocator->recycler_head == chunk) { + if (free_chunk->next == chunk) { + allocator->recycler_head = NULL; + } + else { + allocator->recycler_head = free_chunk->next; + } + } + else if (allocator->master_head == chunk) { + allocator->master_head = free_chunk->next; + } + wmem_free(NULL, cur); + } + else { + /* part of this block is used, so add it to the new block list */ + wmem_block_add_to_block_list(allocator, cur); + } + + cur = next; + } +} + +static void +wmem_block_allocator_cleanup(void *private_data) +{ + /* wmem guarantees that free_all() is called directly before this, so + * calling gc will return all our blocks to the OS automatically */ + wmem_block_gc(private_data); + + /* then just free the allocator structs */ + wmem_free(NULL, private_data); +} + +void +wmem_block_allocator_init(wmem_allocator_t *allocator) +{ + wmem_block_allocator_t *block_allocator; + + block_allocator = wmem_new(NULL, wmem_block_allocator_t); + + allocator->walloc = &wmem_block_alloc; + allocator->wrealloc = &wmem_block_realloc; + allocator->wfree = &wmem_block_free; + + allocator->free_all = &wmem_block_free_all; + allocator->gc = &wmem_block_gc; + allocator->cleanup = &wmem_block_allocator_cleanup; + + allocator->private_data = (void*) block_allocator; + + block_allocator->block_list = NULL; + block_allocator->master_head = NULL; + block_allocator->recycler_head = NULL; +} + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_allocator_block.h b/wsutil/wmem/wmem_allocator_block.h new file mode 100644 index 00000000..e7018dfb --- /dev/null +++ b/wsutil/wmem/wmem_allocator_block.h @@ -0,0 +1,46 @@ +/** @file + * + * Definitions for the Wireshark Memory Manager Large-Block Allocator + * Copyright 2012, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#ifndef __WMEM_ALLOCATOR_BLOCK_H__ +#define __WMEM_ALLOCATOR_BLOCK_H__ + +#include "wmem_core.h" + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +void +wmem_block_allocator_init(wmem_allocator_t *allocator); + +/* Exposed only for testing purposes */ +void +wmem_block_verify(wmem_allocator_t *allocator); + +#ifdef __cplusplus +} +#endif /* __cplusplus */ + +#endif /* __WMEM_ALLOCATOR_BLOCK_H__ */ + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_allocator_block_fast.c b/wsutil/wmem/wmem_allocator_block_fast.c new file mode 100644 index 00000000..538f5187 --- /dev/null +++ b/wsutil/wmem/wmem_allocator_block_fast.c @@ -0,0 +1,261 @@ +/* wmem_allocator_block.c + * Wireshark Memory Manager Fast Large-Block Allocator + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#include "config.h" + +#include +#include + +#include + +#include "wmem_core.h" +#include "wmem_allocator.h" +#include "wmem_allocator_block_fast.h" + +/* https://mail.gnome.org/archives/gtk-devel-list/2004-December/msg00091.html + * The 2*sizeof(size_t) alignment here is borrowed from GNU libc, so it should + * be good most everywhere. It is more conservative than is needed on some + * 64-bit platforms, but ia64 does require a 16-byte alignment. The SIMD + * extensions for x86 and ppc32 would want a larger alignment than this, but + * we don't need to do better than malloc. + */ +#define WMEM_ALIGN_AMOUNT (2 * sizeof (size_t)) +#define WMEM_ALIGN_SIZE(SIZE) ((~(WMEM_ALIGN_AMOUNT-1)) & \ + ((SIZE) + (WMEM_ALIGN_AMOUNT-1))) + +#define WMEM_CHUNK_TO_DATA(CHUNK) ((void*)((uint8_t*)(CHUNK) + WMEM_CHUNK_HEADER_SIZE)) +#define WMEM_DATA_TO_CHUNK(DATA) ((wmem_block_fast_chunk_t*)((uint8_t*)(DATA) - WMEM_CHUNK_HEADER_SIZE)) + +#define WMEM_BLOCK_MAX_ALLOC_SIZE (WMEM_BLOCK_SIZE - (WMEM_BLOCK_HEADER_SIZE + WMEM_CHUNK_HEADER_SIZE)) + +/* When required, allocate more memory from the OS in chunks of this size. + * 2MB is a pretty arbitrary value - it's big enough that it should last a while + * and small enough that a mostly-unused one doesn't waste *too* much. It's + * also a nice power of two, of course. */ +#define WMEM_BLOCK_SIZE (2 * 1024 * 1024) + +/* The header for an entire OS-level 'block' of memory */ +typedef struct _wmem_block_fast_hdr { + struct _wmem_block_fast_hdr *next; + + int32_t pos; +} wmem_block_fast_hdr_t; +#define WMEM_BLOCK_HEADER_SIZE WMEM_ALIGN_SIZE(sizeof(wmem_block_fast_hdr_t)) + +typedef struct { + uint32_t len; +} wmem_block_fast_chunk_t; +#define WMEM_CHUNK_HEADER_SIZE WMEM_ALIGN_SIZE(sizeof(wmem_block_fast_chunk_t)) + +#define JUMBO_MAGIC 0xFFFFFFFF +typedef struct _wmem_block_fast_jumbo { + struct _wmem_block_fast_jumbo *prev, *next; +} wmem_block_fast_jumbo_t; +#define WMEM_JUMBO_HEADER_SIZE WMEM_ALIGN_SIZE(sizeof(wmem_block_fast_jumbo_t)) + +typedef struct { + wmem_block_fast_hdr_t *block_list; + wmem_block_fast_jumbo_t *jumbo_list; +} wmem_block_fast_allocator_t; + +/* Creates a new block, and initializes it. */ +static inline void +wmem_block_fast_new_block(wmem_block_fast_allocator_t *allocator) +{ + wmem_block_fast_hdr_t *block; + + /* allocate/initialize the new block and add it to the block list */ + block = (wmem_block_fast_hdr_t *)wmem_alloc(NULL, WMEM_BLOCK_SIZE); + + block->pos = WMEM_BLOCK_HEADER_SIZE; + block->next = allocator->block_list; + + allocator->block_list = block; +} + +/* API */ + +static void * +wmem_block_fast_alloc(void *private_data, const size_t size) +{ + wmem_block_fast_allocator_t *allocator = (wmem_block_fast_allocator_t*) private_data; + wmem_block_fast_chunk_t *chunk; + int32_t real_size; + + if (size > WMEM_BLOCK_MAX_ALLOC_SIZE) { + wmem_block_fast_jumbo_t *block; + + /* allocate/initialize a new block of the necessary size */ + block = (wmem_block_fast_jumbo_t *)wmem_alloc(NULL, + size + WMEM_JUMBO_HEADER_SIZE + WMEM_CHUNK_HEADER_SIZE); + + block->next = allocator->jumbo_list; + if (block->next) { + block->next->prev = block; + } + block->prev = NULL; + allocator->jumbo_list = block; + + chunk = ((wmem_block_fast_chunk_t*)((uint8_t*)(block) + WMEM_JUMBO_HEADER_SIZE)); + chunk->len = JUMBO_MAGIC; + + return WMEM_CHUNK_TO_DATA(chunk); + } + + real_size = (int32_t)(WMEM_ALIGN_SIZE(size) + WMEM_CHUNK_HEADER_SIZE); + + /* Allocate a new block if necessary. */ + if (!allocator->block_list || + (WMEM_BLOCK_SIZE - allocator->block_list->pos) < real_size) { + wmem_block_fast_new_block(allocator); + } + + chunk = (wmem_block_fast_chunk_t *) ((uint8_t *) allocator->block_list + allocator->block_list->pos); + /* safe to cast, size smaller than WMEM_BLOCK_MAX_ALLOC_SIZE */ + chunk->len = (uint32_t) size; + + allocator->block_list->pos += real_size; + + /* and return the user's pointer */ + return WMEM_CHUNK_TO_DATA(chunk); +} + +static void +wmem_block_fast_free(void *private_data _U_, void *ptr _U_) +{ + /* free is NOP */ +} + +static void * +wmem_block_fast_realloc(void *private_data, void *ptr, const size_t size) +{ + wmem_block_fast_chunk_t *chunk; + + chunk = WMEM_DATA_TO_CHUNK(ptr); + + if (chunk->len == JUMBO_MAGIC) { + wmem_block_fast_jumbo_t *block; + + block = ((wmem_block_fast_jumbo_t*)((uint8_t*)(chunk) - WMEM_JUMBO_HEADER_SIZE)); + block = (wmem_block_fast_jumbo_t*)wmem_realloc(NULL, block, + size + WMEM_JUMBO_HEADER_SIZE + WMEM_CHUNK_HEADER_SIZE); + if (block->prev) { + block->prev->next = block; + } + else { + wmem_block_fast_allocator_t *allocator = (wmem_block_fast_allocator_t*) private_data; + allocator->jumbo_list = block; + } + if (block->next) { + block->next->prev = block; + } + return ((void*)((uint8_t*)(block) + WMEM_JUMBO_HEADER_SIZE + WMEM_CHUNK_HEADER_SIZE)); + } + else if (chunk->len < size) { + /* grow */ + void *newptr; + + /* need to alloc and copy; free is no-op, so don't call it */ + newptr = wmem_block_fast_alloc(private_data, size); + memcpy(newptr, ptr, chunk->len); + + return newptr; + } + + /* shrink or same space - great we can do nothing */ + return ptr; +} + +static void +wmem_block_fast_free_all(void *private_data) +{ + wmem_block_fast_allocator_t *allocator = (wmem_block_fast_allocator_t*) private_data; + wmem_block_fast_hdr_t *cur, *nxt; + wmem_block_fast_jumbo_t *cur_jum, *nxt_jum; + + /* iterate through the blocks, freeing all but the first and reinitializing + * that one */ + cur = allocator->block_list; + + if (cur) { + cur->pos = WMEM_BLOCK_HEADER_SIZE; + nxt = cur->next; + cur->next = NULL; + cur = nxt; + } + + while (cur) { + nxt = cur->next; + wmem_free(NULL, cur); + cur = nxt; + } + + /* now do the jumbo blocks, freeing all of them */ + cur_jum = allocator->jumbo_list; + while (cur_jum) { + nxt_jum = cur_jum->next; + wmem_free(NULL, cur_jum); + cur_jum = nxt_jum; + } + allocator->jumbo_list = NULL; +} + +static void +wmem_block_fast_gc(void *private_data _U_) +{ + /* No-op */ +} + +static void +wmem_block_fast_allocator_cleanup(void *private_data) +{ + wmem_block_fast_allocator_t *allocator = (wmem_block_fast_allocator_t*) private_data; + + /* wmem guarantees that free_all() is called directly before this, so + * simply free the first block */ + wmem_free(NULL, allocator->block_list); + + /* then just free the allocator structs */ + wmem_free(NULL, private_data); +} + +void +wmem_block_fast_allocator_init(wmem_allocator_t *allocator) +{ + wmem_block_fast_allocator_t *block_allocator; + + block_allocator = wmem_new(NULL, wmem_block_fast_allocator_t); + + allocator->walloc = &wmem_block_fast_alloc; + allocator->wrealloc = &wmem_block_fast_realloc; + allocator->wfree = &wmem_block_fast_free; + + allocator->free_all = &wmem_block_fast_free_all; + allocator->gc = &wmem_block_fast_gc; + allocator->cleanup = &wmem_block_fast_allocator_cleanup; + + allocator->private_data = (void*) block_allocator; + + block_allocator->block_list = NULL; + block_allocator->jumbo_list = NULL; +} + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_allocator_block_fast.h b/wsutil/wmem/wmem_allocator_block_fast.h new file mode 100644 index 00000000..ff5f90cd --- /dev/null +++ b/wsutil/wmem/wmem_allocator_block_fast.h @@ -0,0 +1,41 @@ +/** @file + * + * Definitions for the Wireshark Memory Manager Fast Large-Block Allocator + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#ifndef __WMEM_ALLOCATOR_BLOCK_FAST_H__ +#define __WMEM_ALLOCATOR_BLOCK_FAST_H__ + +#include "wmem_core.h" + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +void +wmem_block_fast_allocator_init(wmem_allocator_t *allocator); + +#ifdef __cplusplus +} +#endif /* __cplusplus */ + +#endif /* __WMEM_ALLOCATOR_BLOCK_FAST_H__ */ + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_allocator_simple.c b/wsutil/wmem/wmem_allocator_simple.c new file mode 100644 index 00000000..0c7d9b0b --- /dev/null +++ b/wsutil/wmem/wmem_allocator_simple.c @@ -0,0 +1,152 @@ +/* wmem_allocator_simple.c + * Wireshark Memory Manager Simple Allocator + * Copyright 2012, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#include "config.h" + +#include + +#include + +#include "wmem_core.h" +#include "wmem_allocator.h" +#include "wmem_allocator_simple.h" + +#define DEFAULT_ALLOCS 8192 + +typedef struct _wmem_simple_allocator_t { + int size; + int count; + void **ptrs; +} wmem_simple_allocator_t; + +static void * +wmem_simple_alloc(void *private_data, const size_t size) +{ + wmem_simple_allocator_t *allocator; + + allocator = (wmem_simple_allocator_t*) private_data; + + if (G_UNLIKELY(allocator->count == allocator->size)) { + allocator->size *= 2; + allocator->ptrs = (void**)wmem_realloc(NULL, allocator->ptrs, + sizeof(void*) * allocator->size); + } + + return allocator->ptrs[allocator->count++] = wmem_alloc(NULL, size); +} + +static void +wmem_simple_free(void *private_data, void *ptr) +{ + int i; + wmem_simple_allocator_t *allocator; + + allocator = (wmem_simple_allocator_t*) private_data; + + wmem_free(NULL, ptr); + allocator->count--; + + for (i=allocator->count; i>=0; i--) { + if (ptr == allocator->ptrs[i]) { + if (i < allocator->count) { + allocator->ptrs[i] = allocator->ptrs[allocator->count]; + } + return; + } + } + + g_assert_not_reached(); +} + +static void * +wmem_simple_realloc(void *private_data, void *ptr, const size_t size) +{ + int i; + wmem_simple_allocator_t *allocator; + + allocator = (wmem_simple_allocator_t*) private_data; + + for (i=allocator->count-1; i>=0; i--) { + if (ptr == allocator->ptrs[i]) { + return allocator->ptrs[i] = wmem_realloc(NULL, allocator->ptrs[i], size); + } + } + + g_assert_not_reached(); + /* not reached */ + return NULL; +} + +static void +wmem_simple_free_all(void *private_data) +{ + wmem_simple_allocator_t *allocator; + int i; + + allocator = (wmem_simple_allocator_t*) private_data; + + for (i = 0; icount; i++) { + wmem_free(NULL, allocator->ptrs[i]); + } + allocator->count = 0; +} + +static void +wmem_simple_gc(void *private_data _U_) +{ + /* In this simple allocator, there is nothing to garbage-collect */ +} + +static void +wmem_simple_allocator_cleanup(void *private_data) +{ + wmem_simple_allocator_t *allocator; + + allocator = (wmem_simple_allocator_t*) private_data; + + wmem_free(NULL, allocator->ptrs); + wmem_free(NULL, allocator); +} + +void +wmem_simple_allocator_init(wmem_allocator_t *allocator) +{ + wmem_simple_allocator_t *simple_allocator; + + simple_allocator = wmem_new(NULL, wmem_simple_allocator_t); + + allocator->walloc = &wmem_simple_alloc; + allocator->wrealloc = &wmem_simple_realloc; + allocator->wfree = &wmem_simple_free; + + allocator->free_all = &wmem_simple_free_all; + allocator->gc = &wmem_simple_gc; + allocator->cleanup = &wmem_simple_allocator_cleanup; + + allocator->private_data = (void*) simple_allocator; + + simple_allocator->count = 0; + simple_allocator->size = DEFAULT_ALLOCS; + simple_allocator->ptrs = wmem_alloc_array(NULL, void*, DEFAULT_ALLOCS); +} + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_allocator_simple.h b/wsutil/wmem/wmem_allocator_simple.h new file mode 100644 index 00000000..a843525e --- /dev/null +++ b/wsutil/wmem/wmem_allocator_simple.h @@ -0,0 +1,42 @@ +/** @file + * + * Definitions for the Wireshark Memory Manager Simple Allocator + * Copyright 2012, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#ifndef __WMEM_ALLOCATOR_SIMPLE_H__ +#define __WMEM_ALLOCATOR_SIMPLE_H__ + +#include "wmem_core.h" + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +void +wmem_simple_allocator_init(wmem_allocator_t *allocator); + +#ifdef __cplusplus +} +#endif /* __cplusplus */ + +#endif /* __WMEM_ALLOCATOR_SIMPLE_H__ */ + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_allocator_strict.c b/wsutil/wmem/wmem_allocator_strict.c new file mode 100644 index 00000000..87ef01e2 --- /dev/null +++ b/wsutil/wmem/wmem_allocator_strict.c @@ -0,0 +1,230 @@ +/* wmem_allocator_strict.c + * Wireshark Memory Manager Strict Allocator + * Copyright 2012, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#include "config.h" + +#include + +#include + +#include "wmem_core.h" +#include "wmem_allocator.h" +#include "wmem_allocator_strict.h" + +/* In this allocator, we do everything we can to catch invalid memory accesses. + * This includes using canaries (what Valgrind calls redzones) and + * filling allocated and freed memory with garbage. Valgrind is still the + * better tool on the platforms where it is available - use it instead if + * possible. + */ + +#define WMEM_CANARY_SIZE 8 /* in bytes */ +#define WMEM_CANARY_VALUE 0x9E + +#define WMEM_PREFILL 0xA1 +#define WMEM_POSTFILL 0x1A + +typedef struct _wmem_strict_allocator_block_t { + struct _wmem_strict_allocator_block_t *prev, *next; + + /* Just the length of real_data, not counting the canaries */ + size_t data_len; +} wmem_strict_allocator_block_t; + +#define WMEM_DATA_TO_BLOCK(DATA) ((wmem_strict_allocator_block_t*)((uint8_t*)(DATA) - WMEM_CANARY_SIZE - sizeof(wmem_strict_allocator_block_t))) +#define WMEM_BLOCK_TO_DATA(BLOCK) ((void*)((uint8_t*)(BLOCK) + WMEM_CANARY_SIZE + sizeof(wmem_strict_allocator_block_t))) +#define WMEM_BLOCK_TO_PRE_CANARY(BLOCK) ((uint8_t*)(BLOCK) + sizeof(wmem_strict_allocator_block_t)) +#define WMEM_BLOCK_TO_POST_CANARY(BLOCK) ((uint8_t*)(BLOCK) + WMEM_CANARY_SIZE + sizeof(wmem_strict_allocator_block_t) + (BLOCK)->data_len) +#define WMEM_FULL_SIZE(SIZE) ((SIZE) + sizeof(wmem_strict_allocator_block_t) + (2*WMEM_CANARY_SIZE)) + +typedef struct _wmem_strict_allocator_t { + wmem_strict_allocator_block_t *blocks; +} wmem_strict_allocator_t; + +/* + * some internal helper functions + */ +static inline void +wmem_strict_block_check_canaries(wmem_strict_allocator_block_t *block) +{ + unsigned i; + uint8_t *canary; + + canary = WMEM_BLOCK_TO_PRE_CANARY(block); + for (i=0; idata_len = size; + + memset(WMEM_BLOCK_TO_DATA(block), WMEM_PREFILL, block->data_len); + + canary = WMEM_BLOCK_TO_PRE_CANARY(block); + for (i=0; iblocks) { + allocator->blocks->prev = block; + } + block->next = allocator->blocks; + block->prev = NULL; + allocator->blocks = block; + + return WMEM_BLOCK_TO_DATA(block); +} + +static void +wmem_strict_free(void *private_data, void *ptr) +{ + wmem_strict_allocator_t *allocator; + wmem_strict_allocator_block_t *block; + + allocator = (wmem_strict_allocator_t*) private_data; + + block = WMEM_DATA_TO_BLOCK(ptr); + + wmem_strict_block_check_canaries(block); + + if (block->next) { + block->next->prev = block->prev; + } + + if (block->prev) { + block->prev->next = block->next; + } + else { + allocator->blocks = block->next; + } + + memset(block, WMEM_POSTFILL, WMEM_FULL_SIZE(block->data_len)); + + wmem_free(NULL, block); +} + +static void * +wmem_strict_realloc(void *private_data, void *ptr, const size_t size) +{ + wmem_strict_allocator_block_t *block; + void *new_ptr; + + block = WMEM_DATA_TO_BLOCK(ptr); + + /* create a new block */ + new_ptr = wmem_strict_alloc(private_data, size); + + /* copy from the old block to the new */ + if (block->data_len > size) { + memcpy(new_ptr, ptr, size); + } + else { + memcpy(new_ptr, ptr, block->data_len); + } + + /* free the old block */ + wmem_strict_free(private_data, ptr); + + return new_ptr; +} + +void +wmem_strict_check_canaries(wmem_allocator_t *allocator) +{ + wmem_strict_allocator_t *private_allocator; + wmem_strict_allocator_block_t *block; + + if (allocator->type != WMEM_ALLOCATOR_STRICT) { + return; + } + + private_allocator = (wmem_strict_allocator_t*) allocator->private_data; + + block = private_allocator->blocks; + while (block) { + wmem_strict_block_check_canaries(block); + block = block->next; + } +} + +static void +wmem_strict_free_all(void *private_data) +{ + wmem_strict_allocator_t *allocator; + + allocator = (wmem_strict_allocator_t*) private_data; + + while (allocator->blocks) { + wmem_strict_free(private_data, WMEM_BLOCK_TO_DATA(allocator->blocks)); + } +} + +static void +wmem_strict_gc(void *private_data _U_) +{ + /* We don't really have anything to garbage-collect, but it might be worth + * checking our canaries at this point? */ +} + +static void +wmem_strict_allocator_cleanup(void *private_data) +{ + wmem_free(NULL, private_data); +} + +void +wmem_strict_allocator_init(wmem_allocator_t *allocator) +{ + wmem_strict_allocator_t *strict_allocator; + + strict_allocator = wmem_new(NULL, wmem_strict_allocator_t); + + allocator->walloc = &wmem_strict_alloc; + allocator->wrealloc = &wmem_strict_realloc; + allocator->wfree = &wmem_strict_free; + + allocator->free_all = &wmem_strict_free_all; + allocator->gc = &wmem_strict_gc; + allocator->cleanup = &wmem_strict_allocator_cleanup; + + allocator->private_data = (void*) strict_allocator; + + strict_allocator->blocks = NULL; +} + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_allocator_strict.h b/wsutil/wmem/wmem_allocator_strict.h new file mode 100644 index 00000000..014f76fb --- /dev/null +++ b/wsutil/wmem/wmem_allocator_strict.h @@ -0,0 +1,45 @@ +/** @file + * + * Definitions for the Wireshark Memory Manager Strict Allocator + * Copyright 2012, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#ifndef __WMEM_ALLOCATOR_STRICT_H__ +#define __WMEM_ALLOCATOR_STRICT_H__ + +#include "wmem_core.h" + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +void +wmem_strict_allocator_init(wmem_allocator_t *allocator); + +void +wmem_strict_check_canaries(wmem_allocator_t *allocator); + +#ifdef __cplusplus +} +#endif /* __cplusplus */ + +#endif /* __WMEM_ALLOCATOR_STRICT_H__ */ + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_array.c b/wsutil/wmem/wmem_array.c new file mode 100644 index 00000000..47f6e8e0 --- /dev/null +++ b/wsutil/wmem/wmem_array.c @@ -0,0 +1,196 @@ +/* wmem_array.c + * Wireshark Memory Manager Array + * Copyright 2013, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#include "config.h" + +#include +#include +#include + +#include "wmem_core.h" +#include "wmem_array.h" + +/* Holds a wmem-allocated array. + * elem_len is the size of each element + * elem_count is the number of used elements + * alloc_count is the length (in elems) of the raw buffer pointed to by buf, + * regardless of how many elems are used (the contents) + */ +struct _wmem_array_t { + wmem_allocator_t *allocator; + + uint8_t *buf; + + size_t elem_size; + + unsigned elem_count; + unsigned alloc_count; + + bool null_terminated; +}; + +wmem_array_t * +wmem_array_sized_new(wmem_allocator_t *allocator, size_t elem_size, + unsigned alloc_count) +{ + wmem_array_t *array; + + array = wmem_new(allocator, wmem_array_t); + + array->allocator = allocator; + array->elem_size = elem_size; + array->elem_count = 0; + array->alloc_count = alloc_count ? alloc_count : 1; + array->null_terminated = false; + + array->buf = (uint8_t *)wmem_alloc(array->allocator, + array->elem_size * array->alloc_count); + + return array; +} + +wmem_array_t * +wmem_array_new(wmem_allocator_t *allocator, const size_t elem_size) +{ + wmem_array_t *array; + + array = wmem_array_sized_new(allocator, elem_size, 1); + + return array; +} + +void +wmem_array_grow(wmem_array_t *array, const unsigned to_add) +{ + unsigned new_alloc_count, new_count; + + new_alloc_count = array->alloc_count; + new_count = array->elem_count + to_add; + + while (new_alloc_count < new_count) { + new_alloc_count *= 2; + } + + if (new_alloc_count == array->alloc_count) { + return; + } + + array->buf = (uint8_t *)wmem_realloc(array->allocator, array->buf, + new_alloc_count * array->elem_size); + + array->alloc_count = new_alloc_count; +} + +static void +wmem_array_write_null_terminator(wmem_array_t *array) +{ + if (array->null_terminated) { + wmem_array_grow(array, 1); + memset(&array->buf[array->elem_count * array->elem_size], 0x0, array->elem_size); + } +} + +void +wmem_array_set_null_terminator(wmem_array_t *array) +{ + array->null_terminated = true; + wmem_array_write_null_terminator(array); +} + +void +wmem_array_bzero(wmem_array_t *array) +{ + memset(array->buf, 0x0, array->elem_size * array->elem_count); +} + +void +wmem_array_append(wmem_array_t *array, const void *in, unsigned count) +{ + wmem_array_grow(array, count); + + memcpy(&array->buf[array->elem_count * array->elem_size], in, + count * array->elem_size); + + array->elem_count += count; + + wmem_array_write_null_terminator(array); +} + +void * +wmem_array_index(wmem_array_t *array, unsigned array_index) +{ + g_assert(array_index < array->elem_count); + return &array->buf[array_index * array->elem_size]; +} + +int +wmem_array_try_index(wmem_array_t *array, unsigned array_index, void *val) +{ + if (array_index >= array->elem_count) + return -1; + memcpy(val, &array->buf[array_index * array->elem_size], array->elem_size); + return 0; +} + +void +wmem_array_sort(wmem_array_t *array, int (*compar)(const void*,const void*)) +{ + qsort(array->buf, array->elem_count, array->elem_size, compar); +} + +void * +wmem_array_get_raw(wmem_array_t *array) +{ + return array->buf; +} + +unsigned +wmem_array_get_count(wmem_array_t *array) +{ + if (array == NULL) + return 0; + + return array->elem_count; +} + +void * +wmem_array_finalize(wmem_array_t *array) +{ + if (array == NULL) + return NULL; + + size_t used_size = array->null_terminated ? (array->elem_count + 1) * array->elem_size : array->elem_count * array->elem_size; + void *ret = wmem_realloc(array->allocator, array->buf, used_size); + + wmem_free(array->allocator, array); + + return ret; +} + +void +wmem_destroy_array(wmem_array_t *array) +{ + wmem_free(array->allocator, array->buf); + wmem_free(array->allocator, array); +} + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_array.h b/wsutil/wmem/wmem_array.h new file mode 100644 index 00000000..e813232d --- /dev/null +++ b/wsutil/wmem/wmem_array.h @@ -0,0 +1,121 @@ +/** @file + * Definitions for the Wireshark Memory Manager Array + * Copyright 2013, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#ifndef __WMEM_ARRAY_H__ +#define __WMEM_ARRAY_H__ + +#include +#include + +#include "wmem_core.h" + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +/** @addtogroup wmem + * @{ + * @defgroup wmem-array Array + * + * A resizable array implementation on top of wmem. + * + * @{ + */ + +struct _wmem_array_t; + +typedef struct _wmem_array_t wmem_array_t; + +WS_DLL_PUBLIC +wmem_array_t * +wmem_array_sized_new(wmem_allocator_t *allocator, size_t elem_size, + unsigned alloc_count) +G_GNUC_MALLOC; + +WS_DLL_PUBLIC +wmem_array_t * +wmem_array_new(wmem_allocator_t *allocator, const size_t elem_size) +G_GNUC_MALLOC; + +WS_DLL_PUBLIC +void +wmem_array_grow(wmem_array_t *array, const unsigned to_add); + +WS_DLL_PUBLIC +void +wmem_array_set_null_terminator(wmem_array_t *array); + +WS_DLL_PUBLIC +void +wmem_array_bzero(wmem_array_t *array); + +WS_DLL_PUBLIC +void +wmem_array_append(wmem_array_t *array, const void *in, unsigned count); + +#define wmem_array_append_one(ARRAY, VAL) \ + wmem_array_append((ARRAY), &(VAL), 1) + +WS_DLL_PUBLIC +void * +wmem_array_index(wmem_array_t *array, unsigned array_index); + +WS_DLL_PUBLIC +int +wmem_array_try_index(wmem_array_t *array, unsigned array_index, void *val); + +WS_DLL_PUBLIC +void +wmem_array_sort(wmem_array_t *array, int (*compar)(const void*,const void*)); + +WS_DLL_PUBLIC +void * +wmem_array_get_raw(wmem_array_t *array); + +WS_DLL_PUBLIC +unsigned +wmem_array_get_count(wmem_array_t *array); + +/* Truncates the underlying array to the elements contained within + * (including null terminator if set), frees the wmem_array_t + * structure, and returns a pointer to the raw array. The wmem_array_t + * struct cannot be used after this is called. This is for when you are + * done adding elements to the array but still need the underlying array. + */ +WS_DLL_PUBLIC +void * +wmem_array_finalize(wmem_array_t *array); + +WS_DLL_PUBLIC +void +wmem_destroy_array(wmem_array_t *array); + +/** @} + * @} */ + +#ifdef __cplusplus +} +#endif /* __cplusplus */ + +#endif /* __WMEM_ARRAY_H__ */ + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_core.c b/wsutil/wmem/wmem_core.c new file mode 100644 index 00000000..a166bf84 --- /dev/null +++ b/wsutil/wmem/wmem_core.c @@ -0,0 +1,240 @@ +/* wmem_core.c + * Wireshark Memory Manager Core + * Copyright 2012, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#include +#include +#include + +#include "wmem-int.h" +#include "wmem_core.h" +#include "wmem_map_int.h" +#include "wmem_user_cb_int.h" +#include "wmem_allocator.h" +#include "wmem_allocator_simple.h" +#include "wmem_allocator_block.h" +#include "wmem_allocator_block_fast.h" +#include "wmem_allocator_strict.h" + +/* Set according to the WIRESHARK_DEBUG_WMEM_OVERRIDE environment variable in + * wmem_init. Should not be set again. */ +static bool do_override = false; +static wmem_allocator_type_t override_type; + +void * +wmem_alloc(wmem_allocator_t *allocator, const size_t size) +{ + if (allocator == NULL) { + return g_malloc(size); + } + + ws_assert(allocator->in_scope); + + if (size == 0) { + return NULL; + } + + return allocator->walloc(allocator->private_data, size); +} + +void * +wmem_alloc0(wmem_allocator_t *allocator, const size_t size) +{ + void *buf; + + buf = wmem_alloc(allocator, size); + + if (buf) { + memset(buf, 0, size); + } + + return buf; +} + +void +wmem_free(wmem_allocator_t *allocator, void *ptr) +{ + if (allocator == NULL) { + g_free(ptr); + return; + } + + ws_assert(allocator->in_scope); + + if (ptr == NULL) { + return; + } + + allocator->wfree(allocator->private_data, ptr); +} + +void * +wmem_realloc(wmem_allocator_t *allocator, void *ptr, const size_t size) +{ + if (allocator == NULL) { + return g_realloc(ptr, size); + } + + if (ptr == NULL) { + return wmem_alloc(allocator, size); + } + + if (size == 0) { + wmem_free(allocator, ptr); + return NULL; + } + + ws_assert(allocator->in_scope); + + return allocator->wrealloc(allocator->private_data, ptr, size); +} + +static void +wmem_free_all_real(wmem_allocator_t *allocator, bool final) +{ + wmem_call_callbacks(allocator, + final ? WMEM_CB_DESTROY_EVENT : WMEM_CB_FREE_EVENT); + allocator->free_all(allocator->private_data); +} + +void +wmem_free_all(wmem_allocator_t *allocator) +{ + wmem_free_all_real(allocator, false); +} + +void +wmem_gc(wmem_allocator_t *allocator) +{ + allocator->gc(allocator->private_data); +} + +void +wmem_destroy_allocator(wmem_allocator_t *allocator) +{ + + wmem_free_all_real(allocator, true); + allocator->cleanup(allocator->private_data); + wmem_free(NULL, allocator); +} + +wmem_allocator_t * +wmem_allocator_new(const wmem_allocator_type_t type) +{ + wmem_allocator_t *allocator; + wmem_allocator_type_t real_type; + + if (do_override) { + real_type = override_type; + } + else { + real_type = type; + } + + allocator = wmem_new(NULL, wmem_allocator_t); + allocator->type = real_type; + allocator->callbacks = NULL; + allocator->in_scope = true; + + switch (real_type) { + case WMEM_ALLOCATOR_SIMPLE: + wmem_simple_allocator_init(allocator); + break; + case WMEM_ALLOCATOR_BLOCK: + wmem_block_allocator_init(allocator); + break; + case WMEM_ALLOCATOR_BLOCK_FAST: + wmem_block_fast_allocator_init(allocator); + break; + case WMEM_ALLOCATOR_STRICT: + wmem_strict_allocator_init(allocator); + break; + default: + g_assert_not_reached(); + break; + }; + + return allocator; +} + +void +wmem_init(void) +{ + const char *override_env; + + /* Our valgrind script uses this environment variable to override the + * usual allocator choice so that everything goes through system-level + * allocations that it understands and can track. Otherwise it will get + * confused by the block allocator etc. */ + override_env = getenv("WIRESHARK_DEBUG_WMEM_OVERRIDE"); + + if (override_env == NULL) { + do_override = false; + } + else { + do_override = true; + if (strncmp(override_env, "simple", strlen("simple")) == 0) { + override_type = WMEM_ALLOCATOR_SIMPLE; + } + else if (strncmp(override_env, "block", strlen("block")) == 0) { + override_type = WMEM_ALLOCATOR_BLOCK; + } + else if (strncmp(override_env, "strict", strlen("strict")) == 0) { + override_type = WMEM_ALLOCATOR_STRICT; + } + else if (strncmp(override_env, "block_fast", strlen("block_fast")) == 0) { + override_type = WMEM_ALLOCATOR_BLOCK_FAST; + } + else { + g_warning("Unrecognized wmem override"); + do_override = false; + } + } + + wmem_init_hashing(); +} + +void +wmem_cleanup(void) +{ +} + +void +wmem_enter_scope(wmem_allocator_t *allocator) +{ + allocator->in_scope = true; +} + +void +wmem_leave_scope(wmem_allocator_t *allocator) +{ + wmem_free_all(allocator); + allocator->in_scope = false; +} + +bool +wmem_in_scope(wmem_allocator_t *allocator) +{ + return allocator->in_scope; +} + + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_core.h b/wsutil/wmem/wmem_core.h new file mode 100644 index 00000000..2f423133 --- /dev/null +++ b/wsutil/wmem/wmem_core.h @@ -0,0 +1,252 @@ +/** @file + * Definitions for the Wireshark Memory Manager Core + * Copyright 2012, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#ifndef __WMEM_CORE_H__ +#define __WMEM_CORE_H__ + +#include +#include +#include +#include +#include +#include +#include + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +/** @defgroup wmem Wireshark Memory Manager + * + * Wmem is a memory management framework for Wireshark that makes it simple to + * write dissectors (and other 'user-space' code) that doesn't leak memory. The + * core module provides basic functions like malloc, realloc and free, but + * many other functions are available (see the "Modules" list at the top of + * the generated doxygen HTML). + * + * Any wmem functions which allocate memory are guaranteed to either succeed or + * abort the program. However, they *can* still legally return NULL when the + * amount of requested memory is zero. + * + * @{ + */ + +struct _wmem_allocator_t; +/** A public opaque type representing one wmem allocation pool. */ +typedef struct _wmem_allocator_t wmem_allocator_t; + +/** An enumeration of the different types of available allocators. */ +typedef enum _wmem_allocator_type_t { + WMEM_ALLOCATOR_SIMPLE, /**< A trivial allocator that mallocs requested + memory and tracks allocations via a hash table. As simple as + possible, intended more as a demo than for practical usage. Also + has the benefit of being friendly to tools like valgrind. */ + WMEM_ALLOCATOR_BLOCK, /**< A block allocator that grabs large chunks of + memory at a time (8 MB currently) and serves allocations out of + those chunks. Designed for efficiency, especially in the + free_all operation. */ + WMEM_ALLOCATOR_STRICT, /**< An allocator that does its best to find invalid + memory usage via things like canaries and scrubbing freed + memory. Valgrind is the better choice on platforms that support + it. */ + WMEM_ALLOCATOR_BLOCK_FAST /**< A block allocator like WMEM_ALLOCATOR_BLOCK + but even faster by tracking absolutely minimal metadata and + making 'free' a no-op. Useful only for very short-lived scopes + where there's no reason to free individual allocations because + the next free_all is always just around the corner. */ +} wmem_allocator_type_t; + +/** Allocate the requested amount of memory in the given pool. + * + * @param allocator The allocator object to use to allocate the memory. + * @param size The amount of memory to allocate. + * @return A void pointer to the newly allocated memory. + */ +WS_DLL_PUBLIC +void * +wmem_alloc(wmem_allocator_t *allocator, const size_t size) +G_GNUC_MALLOC; + +/** Allocate memory sufficient to hold one object of the given type. + * + * @param allocator The allocator object to use to allocate the memory. + * @param type The type that the newly allocated memory will hold. + * @return A void pointer to the newly allocated memory. + */ +#define wmem_new(allocator, type) \ + ((type*)wmem_alloc((allocator), sizeof(type))) + +/* + * Overflow-safe multiplication of the size of a type by a number of + * items of that type, returning 0 if the result would overflow (or + * if the number of elements is negative), and the product otherwise. + */ +#define wmem_safe_mult_type_size(type, num) \ + ((((num) <= 0) || ((size_t)sizeof(type) > (G_MAXSSIZE / (size_t)(num)))) ? 0 : (sizeof(type) * (num))) + +/** Allocate memory sufficient to hold n objects of the given type. + * + * @param allocator The allocator object to use to allocate the memory. + * @param type The type that the newly allocated memory will hold. + * @param num The number of objects that the newly allocated memory will hold. + * @return A void pointer to the newly allocated memory. + */ +#define wmem_alloc_array(allocator, type, num) \ + ((type*)wmem_alloc((allocator), wmem_safe_mult_type_size(type, (num)))) + +/** Allocate the requested amount of memory in the given pool. Initializes the + * allocated memory with zeroes. + * + * @param allocator The allocator object to use to allocate the memory. + * @param size The amount of memory to allocate. + * @return A void pointer to the newly allocated and zeroed memory. + */ +WS_DLL_PUBLIC +void * +wmem_alloc0(wmem_allocator_t *allocator, const size_t size) +G_GNUC_MALLOC; + +/** Allocate memory sufficient to hold one object of the given type. + * Initializes the allocated memory with zeroes. + * + * @param allocator The allocator object to use to allocate the memory. + * @param type The type that the newly allocated memory will hold. + * @return A void pointer to the newly allocated and zeroed memory. + */ +#define wmem_new0(allocator, type) \ + ((type*)wmem_alloc0((allocator), sizeof(type))) + +/** Allocate memory sufficient to hold n objects of the given type. + * Initializes the allocated memory with zeroes. + * + * @param allocator The allocator object to use to allocate the memory. + * @param type The type that the newly allocated memory will hold. + * @param num The number of objects that the newly allocated memory will hold. + * @return A void pointer to the newly allocated and zeroed memory. + */ +#define wmem_alloc0_array(allocator, type, num) \ + ((type*)wmem_alloc0((allocator), wmem_safe_mult_type_size(type, (num)))) + +/** Returns the allocated memory to the allocator. This function should only + * be called directly by allocators when the allocated block is sufficiently + * large that the reduced memory usage is worth the cost of the extra function + * call. It's usually easier to just let it get cleaned up when wmem_free_all() + * is called. + * + * @param allocator The allocator object used to originally allocate the memory. + * @param ptr The pointer to the memory block to free. After this function + * returns it no longer points to valid memory. + */ +WS_DLL_PUBLIC +void +wmem_free(wmem_allocator_t *allocator, void *ptr); + +/** Resizes a block of memory, potentially moving it if resizing it in place + * is not possible. + * + * @param allocator The allocator object used to originally allocate the memory. + * @param ptr The pointer to the memory block to resize. + * @param size The new size for the memory block. + * @return The new location of the memory block. If this is different from ptr + * then ptr no longer points to valid memory. + */ +WS_DLL_PUBLIC +void * +wmem_realloc(wmem_allocator_t *allocator, void *ptr, const size_t size) +G_GNUC_MALLOC; + +/** Frees all the memory allocated in a pool. Depending on the allocator + * implementation used this can be significantly cheaper than calling + * wmem_free() on all the individual blocks. It also doesn't require you to have + * external pointers to those blocks. + * + * @param allocator The allocator to free the memory from. + */ +WS_DLL_PUBLIC +void +wmem_free_all(wmem_allocator_t *allocator); + +/** Triggers a garbage-collection in the allocator. This does not free any + * memory, but it can return unused blocks to the operating system or perform + * other optimizations. + * + * @param allocator The allocator in which to trigger the garbage collection. + */ +WS_DLL_PUBLIC +void +wmem_gc(wmem_allocator_t *allocator); + +/** Destroy the given allocator, freeing all memory allocated in it. Once this + * function has been called, no memory allocated with the allocator is valid. + * + * @param allocator The allocator to destroy. + */ +WS_DLL_PUBLIC +void +wmem_destroy_allocator(wmem_allocator_t *allocator); + +/** Create a new allocator of the given type. The type may be overridden by the + * WIRESHARK_DEBUG_WMEM_OVERRIDE environment variable. + * + * @param type The type of allocator to create. + * @return The new allocator. + */ +WS_DLL_PUBLIC +wmem_allocator_t * +wmem_allocator_new(const wmem_allocator_type_t type); + +/** Initialize the wmem subsystem. This must be called before any other wmem + * function, usually at the very beginning of your program. + */ +WS_DLL_PUBLIC +void +wmem_init(void); + +/** Teardown the wmem subsystem. This must be called after all other wmem + * functions, usually at the very end of your program. This function will not + * destroy outstanding allocators, you must do that yourself. + */ +WS_DLL_PUBLIC +void +wmem_cleanup(void); + +WS_DLL_PUBLIC +void +wmem_enter_scope(wmem_allocator_t *allocator); + +WS_DLL_PUBLIC +void +wmem_leave_scope(wmem_allocator_t *allocator); + +WS_DLL_PUBLIC +bool +wmem_in_scope(wmem_allocator_t *allocator); + +/** @} */ + +#ifdef __cplusplus +} +#endif /* __cplusplus */ + +#endif /* __WMEM_CORE_H__ */ + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_interval_tree.c b/wsutil/wmem/wmem_interval_tree.c new file mode 100644 index 00000000..8b28549a --- /dev/null +++ b/wsutil/wmem/wmem_interval_tree.c @@ -0,0 +1,190 @@ +/* wmem_interval_tree.c + * Implements an augmented interval tree + * Based on the red-black tree implementation in epan/wmem.* + * Copyright 2015, Matthieu coudron + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#include "config.h" + +#include +#include +#include +#include +#include + +#include "wmem-int.h" +#include "wmem_core.h" +#include "wmem_tree-int.h" +#include "wmem_strutl.h" +#include "wmem_interval_tree.h" +#include "wmem_user_cb.h" + + +static void +print_range(const void *value) +{ + const wmem_range_t *range = (const wmem_range_t *)value; + if(!value) { + return; + } + printf("Range: low=%" PRIu64 " high=%" PRIu64 " max_edge=%" PRIu64 "\n", range->low, range->high, range->max_edge); +} + +/** + * In an augmented interval tree, each node saves the maximum edge of its child subtrees + * This function compares the children max_edge with the current max_edge + * and propagates any change to the parent nodes. + */ +static void +update_max_edge(wmem_tree_node_t *node) +{ + wmem_range_t *range; + const wmem_range_t *range_l; + const wmem_range_t *range_r; + uint64_t maxEdge = 0; + + if(!node) { + return ; + } + + range = (wmem_range_t *)node->key; + + range_l = (node->left) ? (const wmem_range_t *) (node->left->key) : NULL; + range_r = (node->right) ? (const wmem_range_t *) (node->right->key) : NULL; + + maxEdge = range->high; + + if(range_r) { + maxEdge = MAX(maxEdge, range_r->max_edge) ; + } + if(range_l) { + maxEdge = MAX(maxEdge, range_l->max_edge) ; + } + + /* update the parent nodes only if a change happened (optimization) */ + if(range->max_edge != maxEdge) { + range->max_edge = maxEdge; + update_max_edge(node->parent); + } +} + +bool +wmem_itree_range_overlap(const wmem_range_t *r1, const wmem_range_t *r2) +{ + return (r1->low <= r2->high && r2->low <= r1->high); +} + + +/* after a rotation, some of the children nodes might (dis)appear, thus we need + * to refresh children max_edge. Changes will propagate to parents */ +static void update_edges_after_rotation(wmem_tree_node_t *node) { + if(node->left) update_max_edge(node->left); + if(node->right) update_max_edge(node->right); +} + +wmem_itree_t * +wmem_itree_new(wmem_allocator_t *allocator) +{ + wmem_itree_t *tree = wmem_tree_new(allocator); + tree->post_rotation_cb = &update_edges_after_rotation; + return tree; +} + +bool +wmem_itree_is_empty(wmem_itree_t *tree) +{ + return wmem_tree_is_empty(tree); +} + +static int +wmem_tree_compare_ranges(const wmem_range_t *ra, const wmem_range_t *rb) +{ + if( ra->low == rb->low) { + return 0; + } + else if(ra->low < rb->low) { + return -1; + } + else { + return 1; + } +} + + +void +wmem_itree_insert(wmem_itree_t *tree, const uint64_t low, const uint64_t high, void *data) +{ + wmem_tree_node_t *node; + wmem_range_t *range = (wmem_range_t *)wmem_new(tree->data_allocator, wmem_range_t); + + ws_assert(low <= high); + range->low = low; + range->high = high; + range->max_edge = 0; + + node = wmem_tree_insert(tree, range, data, (compare_func)wmem_tree_compare_ranges); + + /* in absence of rotation, we still need to update max_edge */ + update_max_edge(node); +} + + +static void +wmem_itree_find_intervals_in_subtree(wmem_tree_node_t *node, wmem_range_t requested, wmem_list_t *results) +{ + const wmem_range_t* current; + + if(!node) { + return; + } + current = (wmem_range_t*)node->key; + + /* there is no child that can possibly match */ + if(requested.low > current->max_edge) { + return; + } + + if(wmem_itree_range_overlap(current, &requested)) { + wmem_list_prepend(results, node->data); + } + + wmem_itree_find_intervals_in_subtree(node->left, requested, results); + wmem_itree_find_intervals_in_subtree(node->right, requested, results); +} + +wmem_list_t * +wmem_itree_find_intervals(wmem_itree_t *tree, wmem_allocator_t *allocator, uint64_t low, uint64_t high) +{ + wmem_list_t *results = NULL; + wmem_range_t requested = { low, high, 0 }; + results = wmem_list_new(allocator); + + wmem_itree_find_intervals_in_subtree(tree->root, requested, results); + return results; +} + + +void +wmem_print_itree(wmem_tree_t *tree) +{ + wmem_print_tree(tree, &print_range, NULL); +} + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_interval_tree.h b/wsutil/wmem/wmem_interval_tree.h new file mode 100644 index 00000000..1d7bc4df --- /dev/null +++ b/wsutil/wmem/wmem_interval_tree.h @@ -0,0 +1,101 @@ +/** @file + * Definitions for the Wireshark Memory Manager Red-Black Tree + * Based on the red-black tree implementation in epan/emem.* + * Copyright 2015, Matthieu coudron + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ +#ifndef __WMEM_INTERVAL_TREE_H__ +#define __WMEM_INTERVAL_TREE_H__ + +#include "wmem_core.h" +#include "wmem_tree.h" +#include "wmem_list.h" + + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +/** @addtogroup wmem + * @{ + * @defgroup wmem-interval-tree Interval Tree + * + * http://www.geeksforgeeks.org/interval-tree/ + * The idea is to augment a self-balancing Binary Search Tree (BST) like Red Black Tree, AVL Tree, etc ... + * to maintain a set of intervals so that all operations can be done in O(Logn) time. + * @{ + * Following wikipedia's convention this is an augmented tree rather then an interval tree + * http://www.wikiwand.com/en/Interval_tree + */ + +struct _wmem_tree_t; +typedef struct _wmem_tree_t wmem_itree_t; + +struct _wmem_range_t { + uint64_t low; /* low is used as the key in the binary tree */ + uint64_t high; /* Max value of the range */ + uint64_t max_edge; /* max value among subtrees */ +}; + +WS_DLL_PUBLIC +wmem_itree_t * +wmem_itree_new(wmem_allocator_t *allocator) +G_GNUC_MALLOC; + + +/** Returns true if the tree is empty (has no nodes). */ +WS_DLL_PUBLIC +bool +wmem_itree_is_empty(wmem_itree_t *tree); + + +/** Inserts a range low-high indexed by "low" in O(log(n)). + * As in wmem_tree, if a key "low" already exists, it will be overwritten with the new data + * + */ +WS_DLL_PUBLIC +void +wmem_itree_insert(wmem_itree_t *tree, const uint64_t low, const uint64_t high, void *data); + + +/* + * Save results in a wmem_list with the scope passed as a parameter. + * wmem_list_t is always allocated even if there is no result + */ +WS_DLL_PUBLIC +wmem_list_t * +wmem_itree_find_intervals(wmem_itree_t *tree, wmem_allocator_t *allocator, uint64_t low, uint64_t high); + + +/** + * Print ranges along the tree + */ +void +wmem_print_itree(wmem_itree_t *tree); + +/** @} + * @} */ + +#ifdef __cplusplus +} +#endif /* __cplusplus */ + +#endif /* __WMEM_INTERVAL_TREE_H__ */ + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_list.c b/wsutil/wmem/wmem_list.c new file mode 100644 index 00000000..c03ffe31 --- /dev/null +++ b/wsutil/wmem/wmem_list.c @@ -0,0 +1,276 @@ +/* wmem_list.c + * Wireshark Memory Manager Doubly-Linked List + * Copyright 2012, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#include +#include + +#include "wmem_core.h" +#include "wmem_list.h" + +struct _wmem_list_frame_t { + struct _wmem_list_frame_t *next, *prev; + void *data; +}; + +struct _wmem_list_t { + unsigned count; + wmem_list_frame_t *head, *tail; + wmem_allocator_t *allocator; +}; + +unsigned +wmem_list_count(const wmem_list_t *list) +{ + return list->count; +} + +wmem_list_frame_t * +wmem_list_head(const wmem_list_t *list) +{ + return list->head; +} + +wmem_list_frame_t * +wmem_list_tail(const wmem_list_t *list) +{ + return list->tail; +} + +wmem_list_frame_t * +wmem_list_frame_next(const wmem_list_frame_t *frame) +{ + return frame->next; +} + +wmem_list_frame_t * +wmem_list_frame_prev(const wmem_list_frame_t *frame) +{ + return frame->prev; +} + +void * +wmem_list_frame_data(const wmem_list_frame_t *frame) +{ + return frame->data; +} + +void +wmem_list_remove(wmem_list_t *list, void *data) +{ + wmem_list_frame_t *frame; + + frame = list->head; + + while (frame && frame->data != data) { + frame = frame->next; + } + + if (frame == NULL) { + return; + } + + wmem_list_remove_frame(list, frame); +} + +void +wmem_list_remove_frame(wmem_list_t *list, wmem_list_frame_t *frame) +{ + if (frame->prev) { + frame->prev->next = frame->next; + } + else { + list->head = frame->next; + } + + if (frame->next) { + frame->next->prev = frame->prev; + } + else { + list->tail = frame->prev; + } + + list->count--; + wmem_free(list->allocator, frame); +} + +wmem_list_frame_t * +wmem_list_find(wmem_list_t *list, const void *data) +{ + wmem_list_frame_t *cur; + + for (cur = list->head; cur; cur = cur->next) { + if(cur->data == data) + return cur; + } + + return NULL; +} + +wmem_list_frame_t * +wmem_list_find_custom(wmem_list_t *list, const void *data, GCompareFunc compare_func) +{ + wmem_list_frame_t *cur; + + for (cur = list->head; cur != NULL; cur = cur->next) { + if (compare_func(cur->data, data) == 0) { + return cur; + } + } + + return NULL; +} + +void +wmem_list_prepend(wmem_list_t *list, void *data) +{ + wmem_list_frame_t *new_frame; + + new_frame = wmem_new(list->allocator, wmem_list_frame_t); + + new_frame->data = data; + new_frame->next = list->head; + new_frame->prev = NULL; + + if (list->head) { + list->head->prev = new_frame; + } + else { + list->tail = new_frame; + } + + list->head = new_frame; + list->count++; +} + +void +wmem_list_append(wmem_list_t *list, void *data) +{ + wmem_list_frame_t *new_frame; + + new_frame = wmem_new(list->allocator, wmem_list_frame_t); + new_frame->data = data; + new_frame->next = NULL; + new_frame->prev = list->tail; + + if (list->tail) { + list->tail->next = new_frame; + } + else { + list->head = new_frame; + } + + list->tail = new_frame; + list->count++; +} + +void +wmem_list_insert_sorted(wmem_list_t *list, void* data, GCompareFunc func) +{ + wmem_list_frame_t *new_frame; + wmem_list_frame_t *cur; + wmem_list_frame_t *prev; + + new_frame = wmem_new(list->allocator, wmem_list_frame_t); + new_frame->data = data; + new_frame->next = NULL; + new_frame->prev = NULL; + + list->count++; + + if (!list->head) { + list->head = new_frame; + list->tail = new_frame; + return; + } + + cur = list->head; + + if (func(cur->data, data) >= 0) { + cur->prev = new_frame; + new_frame->next = cur; + list->head = new_frame; + return; + } + + do { + prev = cur; + cur = cur->next; + } while (cur && func(cur->data, data) <= 0); + + if (!cur) { + prev->next = new_frame; + new_frame->prev = prev; + list->tail = new_frame; + return; + } + + new_frame->prev = prev; + new_frame->next = cur; + new_frame->prev->next = new_frame; + new_frame->next->prev = new_frame; +} + +wmem_list_t * +wmem_list_new(wmem_allocator_t *allocator) +{ + wmem_list_t *list; + + list = wmem_new(allocator, wmem_list_t); + + list->count = 0; + list->head = NULL; + list->tail = NULL; + list->allocator = allocator; + + return list; +} + +void +wmem_destroy_list(wmem_list_t *list) +{ + wmem_list_frame_t *cur, *next; + + cur = list->head; + + while (cur) { + next = cur->next; + wmem_free(list->allocator, cur); + cur = next; + } + + wmem_free(list->allocator, list); +} + +void +wmem_list_foreach(wmem_list_t *list, GFunc foreach_func, void * user_data) +{ + wmem_list_frame_t *cur; + + cur = list->head; + + while (cur) { + foreach_func(cur->data, user_data); + cur = cur->next; + } +} + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_list.h b/wsutil/wmem/wmem_list.h new file mode 100644 index 00000000..fc0e5229 --- /dev/null +++ b/wsutil/wmem/wmem_list.h @@ -0,0 +1,128 @@ +/** @file + * Definitions for the Wireshark Memory Manager Doubly-Linked List + * Copyright 2012, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#ifndef __WMEM_LIST_H__ +#define __WMEM_LIST_H__ + +#include +#include + +#include "wmem_core.h" + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +/** @addtogroup wmem + * @{ + * @defgroup wmem-list Doubly-Linked List + * + * A doubly-linked list implementation on top of wmem. + * + * @{ + */ + +struct _wmem_list_t; +struct _wmem_list_frame_t; + +typedef struct _wmem_list_t wmem_list_t; +typedef struct _wmem_list_frame_t wmem_list_frame_t; + +WS_DLL_PUBLIC +unsigned +wmem_list_count(const wmem_list_t *list); + +WS_DLL_PUBLIC +wmem_list_frame_t * +wmem_list_head(const wmem_list_t *list); + +WS_DLL_PUBLIC +wmem_list_frame_t * +wmem_list_tail(const wmem_list_t *list); + +WS_DLL_PUBLIC +wmem_list_frame_t * +wmem_list_frame_next(const wmem_list_frame_t *frame); + +WS_DLL_PUBLIC +wmem_list_frame_t * +wmem_list_frame_prev(const wmem_list_frame_t *frame); + +WS_DLL_PUBLIC +void * +wmem_list_frame_data(const wmem_list_frame_t *frame); + +WS_DLL_PUBLIC +void +wmem_list_remove(wmem_list_t *list, void *data); + +WS_DLL_PUBLIC +void +wmem_list_remove_frame(wmem_list_t *list, wmem_list_frame_t *frame); + +/* + * Linear search, search is O(n) + */ +WS_DLL_PUBLIC +wmem_list_frame_t * +wmem_list_find(wmem_list_t *list, const void *data); + +WS_DLL_PUBLIC +wmem_list_frame_t * +wmem_list_find_custom(wmem_list_t *list, const void *data, GCompareFunc func); + +WS_DLL_PUBLIC +void +wmem_list_prepend(wmem_list_t *list, void *data); + +WS_DLL_PUBLIC +void +wmem_list_append(wmem_list_t *list, void *data); + +WS_DLL_PUBLIC +void +wmem_list_insert_sorted(wmem_list_t *list, void* data, GCompareFunc func); + + +WS_DLL_PUBLIC +wmem_list_t * +wmem_list_new(wmem_allocator_t *allocator) +G_GNUC_MALLOC; + +WS_DLL_PUBLIC +void +wmem_list_foreach(wmem_list_t *list, GFunc foreach_func, void * user_data); + +WS_DLL_PUBLIC +void +wmem_destroy_list(wmem_list_t *list); + +/** @} + * @} */ + +#ifdef __cplusplus +} +#endif /* __cplusplus */ + +#endif /* __WMEM_LIST_H__ */ + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_map.c b/wsutil/wmem/wmem_map.c new file mode 100644 index 00000000..ea76f455 --- /dev/null +++ b/wsutil/wmem/wmem_map.c @@ -0,0 +1,515 @@ +/* wmem_map.c + * Wireshark Memory Manager Hash Map + * Copyright 2014, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ +#include "config.h" + +#include + +#include "wmem_core.h" +#include "wmem_list.h" +#include "wmem_map.h" +#include "wmem_map_int.h" +#include "wmem_user_cb.h" + +static uint32_t x; /* Used for universal integer hashing (see the HASH macro) */ + +/* Used for the wmem_strong_hash() function */ +static uint32_t preseed; +static uint32_t postseed; + +void +wmem_init_hashing(void) +{ + x = g_random_int(); + if (G_UNLIKELY(x == 0)) + x = 1; + + preseed = g_random_int(); + postseed = g_random_int(); +} + +typedef struct _wmem_map_item_t { + const void *key; + void *value; + struct _wmem_map_item_t *next; +} wmem_map_item_t; + +struct _wmem_map_t { + unsigned count; /* number of items stored */ + + /* The base-2 logarithm of the actual size of the table. We store this + * value for efficiency in hashing, since finding the actual capacity + * becomes just a left-shift (see the CAPACITY macro) whereas taking + * logarithms is expensive. */ + size_t capacity; + + wmem_map_item_t **table; + + GHashFunc hash_func; + GEqualFunc eql_func; + + unsigned metadata_scope_cb_id; + unsigned data_scope_cb_id; + + wmem_allocator_t *metadata_allocator; + wmem_allocator_t *data_allocator; +}; + +/* As per the comment on the 'capacity' member of the wmem_map_t struct, this is + * the base-2 logarithm, meaning the actual default capacity is 2^5 = 32 */ +#define WMEM_MAP_DEFAULT_CAPACITY 5 + +/* Macro for calculating the real capacity of the map by using a left-shift to + * do the 2^x operation. */ +#define CAPACITY(MAP) (((size_t)1) << (MAP)->capacity) + +/* Efficient universal integer hashing: + * https://en.wikipedia.org/wiki/Universal_hashing#Avoiding_modular_arithmetic + */ +#define HASH(MAP, KEY) \ + ((uint32_t)(((MAP)->hash_func(KEY) * x) >> (32 - (MAP)->capacity))) + +static void +wmem_map_init_table(wmem_map_t *map) +{ + map->count = 0; + map->capacity = WMEM_MAP_DEFAULT_CAPACITY; + map->table = wmem_alloc0_array(map->data_allocator, wmem_map_item_t*, CAPACITY(map)); +} + +wmem_map_t * +wmem_map_new(wmem_allocator_t *allocator, + GHashFunc hash_func, GEqualFunc eql_func) +{ + wmem_map_t *map; + + map = wmem_new(allocator, wmem_map_t); + + map->hash_func = hash_func; + map->eql_func = eql_func; + map->metadata_allocator = allocator; + map->data_allocator = allocator; + map->count = 0; + map->table = NULL; + + return map; +} + +static bool +wmem_map_reset_cb(wmem_allocator_t *allocator _U_, wmem_cb_event_t event, + void *user_data) +{ + wmem_map_t *map = (wmem_map_t*)user_data; + + map->count = 0; + map->table = NULL; + + if (event == WMEM_CB_DESTROY_EVENT) { + wmem_unregister_callback(map->metadata_allocator, map->metadata_scope_cb_id); + wmem_free(map->metadata_allocator, map); + } + + return true; +} + +static bool +wmem_map_destroy_cb(wmem_allocator_t *allocator _U_, wmem_cb_event_t event _U_, + void *user_data) +{ + wmem_map_t *map = (wmem_map_t*)user_data; + + wmem_unregister_callback(map->data_allocator, map->data_scope_cb_id); + + return false; +} + +wmem_map_t * +wmem_map_new_autoreset(wmem_allocator_t *metadata_scope, wmem_allocator_t *data_scope, + GHashFunc hash_func, GEqualFunc eql_func) +{ + wmem_map_t *map; + + map = wmem_new(metadata_scope, wmem_map_t); + + map->hash_func = hash_func; + map->eql_func = eql_func; + map->metadata_allocator = metadata_scope; + map->data_allocator = data_scope; + map->count = 0; + map->table = NULL; + + map->metadata_scope_cb_id = wmem_register_callback(metadata_scope, wmem_map_destroy_cb, map); + map->data_scope_cb_id = wmem_register_callback(data_scope, wmem_map_reset_cb, map); + + return map; +} + +static inline void +wmem_map_grow(wmem_map_t *map) +{ + wmem_map_item_t **old_table, *cur, *nxt; + size_t old_cap, i; + unsigned slot; + + /* store the old table and capacity */ + old_table = map->table; + old_cap = CAPACITY(map); + + /* double the size (capacity is base-2 logarithm, so this just means + * increment it) and allocate new table */ + map->capacity++; + map->table = wmem_alloc0_array(map->data_allocator, wmem_map_item_t*, CAPACITY(map)); + + /* copy all the elements over from the old table */ + for (i=0; inext; + slot = HASH(map, cur->key); + cur->next = map->table[slot]; + map->table[slot] = cur; + cur = nxt; + } + } + + /* free the old table */ + wmem_free(map->data_allocator, old_table); +} + +void * +wmem_map_insert(wmem_map_t *map, const void *key, void *value) +{ + wmem_map_item_t **item; + void *old_val; + + /* Make sure we have a table */ + if (map->table == NULL) { + wmem_map_init_table(map); + } + + /* get a pointer to the slot */ + item = &(map->table[HASH(map, key)]); + + /* check existing items in that slot */ + while (*item) { + if (map->eql_func(key, (*item)->key)) { + /* replace and return old value for this key */ + old_val = (*item)->value; + (*item)->value = value; + return old_val; + } + item = &((*item)->next); + } + + /* insert new item */ + (*item) = wmem_new(map->data_allocator, wmem_map_item_t); + + (*item)->key = key; + (*item)->value = value; + (*item)->next = NULL; + + map->count++; + + /* increase size if we are over-full */ + if (map->count >= CAPACITY(map)) { + wmem_map_grow(map); + } + + /* no previous entry, return NULL */ + return NULL; +} + +bool +wmem_map_contains(wmem_map_t *map, const void *key) +{ + wmem_map_item_t *item; + + /* Make sure we have a table */ + if (map->table == NULL) { + return false; + } + + /* find correct slot */ + item = map->table[HASH(map, key)]; + + /* scan list of items in this slot for the correct value */ + while (item) { + if (map->eql_func(key, item->key)) { + return true; + } + item = item->next; + } + + return false; +} + +void * +wmem_map_lookup(wmem_map_t *map, const void *key) +{ + wmem_map_item_t *item; + + /* Make sure we have a table */ + if (map->table == NULL) { + return NULL; + } + + /* find correct slot */ + item = map->table[HASH(map, key)]; + + /* scan list of items in this slot for the correct value */ + while (item) { + if (map->eql_func(key, item->key)) { + return item->value; + } + item = item->next; + } + + return NULL; +} + +bool +wmem_map_lookup_extended(wmem_map_t *map, const void *key, const void **orig_key, void **value) +{ + wmem_map_item_t *item; + + /* Make sure we have a table */ + if (map->table == NULL) { + return false; + } + + /* find correct slot */ + item = map->table[HASH(map, key)]; + + /* scan list of items in this slot for the correct value */ + while (item) { + if (map->eql_func(key, item->key)) { + if (orig_key) { + *orig_key = item->key; + } + if (value) { + *value = item->value; + } + return true; + } + item = item->next; + } + + return false; +} + +void * +wmem_map_remove(wmem_map_t *map, const void *key) +{ + wmem_map_item_t **item, *tmp; + void *value; + + /* Make sure we have a table */ + if (map->table == NULL) { + return NULL; + } + + /* get a pointer to the slot */ + item = &(map->table[HASH(map, key)]); + + /* check the items in that slot */ + while (*item) { + if (map->eql_func(key, (*item)->key)) { + /* found it */ + tmp = (*item); + value = tmp->value; + (*item) = tmp->next; + wmem_free(map->data_allocator, tmp); + map->count--; + return value; + } + item = &((*item)->next); + } + + /* didn't find it */ + return NULL; +} + +bool +wmem_map_steal(wmem_map_t *map, const void *key) +{ + wmem_map_item_t **item, *tmp; + + /* Make sure we have a table */ + if (map->table == NULL) { + return false; + } + + /* get a pointer to the slot */ + item = &(map->table[HASH(map, key)]); + + /* check the items in that slot */ + while (*item) { + if (map->eql_func(key, (*item)->key)) { + /* found it */ + tmp = (*item); + (*item) = tmp->next; + map->count--; + return true; + } + item = &((*item)->next); + } + + /* didn't find it */ + return false; +} + +wmem_list_t* +wmem_map_get_keys(wmem_allocator_t *list_allocator, wmem_map_t *map) +{ + size_t capacity, i; + wmem_map_item_t *cur; + wmem_list_t* list = wmem_list_new(list_allocator); + + if (map->table != NULL) { + capacity = CAPACITY(map); + + /* copy all the elements into the list over from table */ + for (i=0; itable[i]; + while (cur) { + wmem_list_prepend(list, (void*)cur->key); + cur = cur->next; + } + } + } + + return list; +} + +void +wmem_map_foreach(wmem_map_t *map, GHFunc foreach_func, void * user_data) +{ + wmem_map_item_t *cur; + unsigned i; + + /* Make sure we have a table */ + if (map->table == NULL) { + return; + } + + for (i = 0; i < CAPACITY(map); i++) { + cur = map->table[i]; + while (cur) { + foreach_func((void *)cur->key, (void *)cur->value, user_data); + cur = cur->next; + } + } +} + +unsigned +wmem_map_foreach_remove(wmem_map_t *map, GHRFunc foreach_func, void * user_data) +{ + wmem_map_item_t **item, *tmp; + unsigned i, deleted = 0; + + /* Make sure we have a table */ + if (map->table == NULL) { + return 0; + } + + for (i = 0; i < CAPACITY(map); i++) { + item = &(map->table[i]); + while (*item) { + if (foreach_func((void *)(*item)->key, (void *)(*item)->value, user_data)) { + tmp = *item; + *item = tmp->next; + wmem_free(map->data_allocator, tmp); + map->count--; + deleted++; + } else { + item = &((*item)->next); + } + } + } + return deleted; +} + +unsigned +wmem_map_size(wmem_map_t *map) +{ + return map->count; +} + +/* Borrowed from Perl 5.18. This is based on Bob Jenkin's one-at-a-time + * algorithm with some additional randomness seeded in. It is believed to be + * generally secure against collision attacks. See + * http://blog.booking.com/hardening-perls-hash-function.html + */ +uint32_t +wmem_strong_hash(const uint8_t *buf, const size_t len) +{ + const uint8_t * const end = (const uint8_t *)buf + len; + uint32_t hash = preseed + (uint32_t)len; + + while (buf < end) { + hash += (hash << 10); + hash ^= (hash >> 6); + hash += *buf++; + } + + hash += (hash << 10); + hash ^= (hash >> 6); + hash += ((uint8_t*)&postseed)[0]; + + hash += (hash << 10); + hash ^= (hash >> 6); + hash += ((uint8_t*)&postseed)[1]; + + hash += (hash << 10); + hash ^= (hash >> 6); + hash += ((uint8_t*)&postseed)[2]; + + hash += (hash << 10); + hash ^= (hash >> 6); + hash += ((uint8_t*)&postseed)[3]; + + hash += (hash << 10); + hash ^= (hash >> 6); + + hash += (hash << 3); + hash ^= (hash >> 11); + return (hash + (hash << 15)); +} + +unsigned +wmem_str_hash(gconstpointer key) +{ + return wmem_strong_hash((const uint8_t *)key, strlen((const char *)key)); +} + +unsigned +wmem_int64_hash(gconstpointer key) +{ + return wmem_strong_hash((const uint8_t *)key, sizeof(uint64_t)); +} + +unsigned +wmem_double_hash(gconstpointer key) +{ + return wmem_strong_hash((const uint8_t *)key, sizeof(double)); +} + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_map.h b/wsutil/wmem/wmem_map.h new file mode 100644 index 00000000..a6886dd4 --- /dev/null +++ b/wsutil/wmem/wmem_map.h @@ -0,0 +1,246 @@ +/** @file + * Definitions for the Wireshark Memory Manager Hash Map + * Copyright 2014, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#ifndef __WMEM_MAP_H__ +#define __WMEM_MAP_H__ + +#include + +#include "wmem_core.h" +#include "wmem_list.h" + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +/** @addtogroup wmem + * @{ + * @defgroup wmem-map Hash Map + * + * A hash map implementation on top of wmem. Provides insertion, deletion and + * lookup in expected amortized constant time. Uses universal hashing to map + * keys into buckets, and provides a generic strong hash function that makes + * it secure against algorithmic complexity attacks, and suitable for use + * even with untrusted data. + * + * @{ + */ + +struct _wmem_map_t; +typedef struct _wmem_map_t wmem_map_t; + +/** Creates a map with the given allocator scope. When the scope is emptied, + * the map is fully destroyed. Items stored in it will not be freed unless they + * were allocated from the same scope. For details on the GHashFunc and + * GEqualFunc parameters, see the glib documentation at: + * https://developer-old.gnome.org/glib/stable/glib-Hash-Tables.html + * + * If the keys are coming from untrusted data, do *not* use glib's default hash + * functions for strings, int64s or doubles. Wmem provides stronger equivalents + * below. Feel free to use the g_direct_hash, g_int_hash, and any of the + * g_*_equal functions though, as they should be safe. + * + * @param allocator The allocator scope with which to create the map. + * @param hash_func The hash function used to place inserted keys. + * @param eql_func The equality function used to compare inserted keys. + * @return The newly-allocated map. + */ +WS_DLL_PUBLIC +wmem_map_t * +wmem_map_new(wmem_allocator_t *allocator, + GHashFunc hash_func, GEqualFunc eql_func) +G_GNUC_MALLOC; + +/** Creates a map with two allocator scopes. The base structure lives in the + * metadata scope, and the map data lives in the data scope. Every time free_all + * occurs in the data scope the map is transparently emptied without affecting + * the location of the base / metadata structure. + * + * WARNING: None of the map (even the part in the metadata scope) can be used + * after the data scope has been *destroyed*. + * + * The primary use for this function is to create maps that reset for each new + * capture file that is loaded. This can be done by specifying wmem_epan_scope() + * as the metadata scope and wmem_file_scope() as the data scope. + */ +WS_DLL_PUBLIC +wmem_map_t * +wmem_map_new_autoreset(wmem_allocator_t *metadata_scope, wmem_allocator_t *data_scope, + GHashFunc hash_func, GEqualFunc eql_func) +G_GNUC_MALLOC; + +/** Inserts a value into the map. + * + * @param map The map to insert into. + * @param key The key to insert by. + * @param value The value to insert. + * @return The previous value stored at this key if any, or NULL. + */ +WS_DLL_PUBLIC +void * +wmem_map_insert(wmem_map_t *map, const void *key, void *value); + +/** Check if a value is in the map. + * + * @param map The map to search in. + * @param key The key to lookup. + * @return true if the key is in the map, otherwise false. + */ +WS_DLL_PUBLIC +bool +wmem_map_contains(wmem_map_t *map, const void *key); + +/** Lookup a value in the map. + * + * @param map The map to search in. + * @param key The key to lookup. + * @return The value stored at the key if any, or NULL. + */ +WS_DLL_PUBLIC +void * +wmem_map_lookup(wmem_map_t *map, const void *key); + +/** Lookup a value in the map, returning the key, value, and a boolean which + * is true if the key is found. + * + * @param map The map to search in. + * @param key The key to lookup. + * @param orig_key (optional) The key that was determined to be a match, if any. + * @param value (optional) The value stored at the key, if any. + * @return true if the key is in the map, otherwise false. + */ +WS_DLL_PUBLIC +bool +wmem_map_lookup_extended(wmem_map_t *map, const void *key, const void **orig_key, void **value); + +/** Remove a value from the map. If no value is stored at that key, nothing + * happens. + * + * @param map The map to remove from. + * @param key The key of the value to remove. + * @return The (removed) value stored at the key if any, or NULL. + */ +WS_DLL_PUBLIC +void * +wmem_map_remove(wmem_map_t *map, const void *key); + +/** Remove a key and value from the map but does not destroy (free) them. If no + * value is stored at that key, nothing happens. + * + * @param map The map to remove from. + * @param key The key of the value to remove. + * @return true if key is found false if not. + */ +WS_DLL_PUBLIC +bool +wmem_map_steal(wmem_map_t *map, const void *key); + +/** Retrieves a list of keys inside the map + * + * @param list_allocator The allocator scope for the returned list. + * @param map The map to extract keys from + * @return list of keys in the map + */ +WS_DLL_PUBLIC +wmem_list_t* +wmem_map_get_keys(wmem_allocator_t *list_allocator, wmem_map_t *map); + +/** Run a function against all key/value pairs in the map. The order + * of the calls is unpredictable, since it is based on the internal + * storage of data. + * + * @param map The map to use + * @param foreach_func the function to call for each key/value pair + * @param user_data user data to pass to the function + */ +WS_DLL_PUBLIC +void +wmem_map_foreach(wmem_map_t *map, GHFunc foreach_func, void * user_data); + +/** Run a function against all key/value pairs in the map. If the + * function returns true, then the key/value pair is removed from + * the map. The order of the calls is unpredictable, since it is + * based on the internal storage of data. + * + * @param map The map to use + * @param foreach_func the function to call for each key/value pair + * @param user_data user data to pass to the function + * @return The number of items removed + */ +WS_DLL_PUBLIC +unsigned +wmem_map_foreach_remove(wmem_map_t *map, GHRFunc foreach_func, void * user_data); + +/** Return the number of elements of the map. + * + * @param map The map to use + * @return the number of elements +*/ +WS_DLL_PUBLIC +unsigned +wmem_map_size(wmem_map_t *map); + +/** Compute a strong hash value for an arbitrary sequence of bytes. Use of this + * hash value should be secure against algorithmic complexity attacks, even for + * short keys. The computation uses a random seed which is generated on wmem + * initialization, so the same key will hash to different values on different + * runs of the application. + * + * @param buf The buffer of bytes (does not have to be aligned). + * @param len The length of buf to use for the hash computation. + * @return The hash value. + */ +WS_DLL_PUBLIC +uint32_t +wmem_strong_hash(const uint8_t *buf, const size_t len); + +/** An implementation of GHashFunc using wmem_strong_hash. Prefer this over + * g_str_hash when the data comes from an untrusted source. + */ +WS_DLL_PUBLIC +unsigned +wmem_str_hash(gconstpointer key); + +/** An implementation of GHashFunc using wmem_strong_hash. Prefer this over + * g_int64_hash when the data comes from an untrusted source. + */ +WS_DLL_PUBLIC +unsigned +wmem_int64_hash(gconstpointer key); + +/** An implementation of GHashFunc using wmem_strong_hash. Prefer this over + * g_double_hash when the data comes from an untrusted source. + */ +WS_DLL_PUBLIC +unsigned +wmem_double_hash(gconstpointer key); + +/** @} + * @} */ + +#ifdef __cplusplus +} +#endif /* __cplusplus */ + +#endif /* __WMEM_MAP_H__ */ + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_map_int.h b/wsutil/wmem/wmem_map_int.h new file mode 100644 index 00000000..2798983a --- /dev/null +++ b/wsutil/wmem/wmem_map_int.h @@ -0,0 +1,41 @@ +/** @file + * + * Definitions for the Wireshark Memory Manager Hash Map Internals + * Copyright 2014, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#ifndef __WMEM_MAP_INT_H__ +#define __WMEM_MAP_INT_H__ + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +WS_DLL_LOCAL +void +wmem_init_hashing(void); + +#ifdef __cplusplus +} +#endif /* __cplusplus */ + +#endif /* __WMEM_MAP_INT_H__ */ + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_miscutl.c b/wsutil/wmem/wmem_miscutl.c new file mode 100644 index 00000000..14426447 --- /dev/null +++ b/wsutil/wmem/wmem_miscutl.c @@ -0,0 +1,55 @@ +/* wmem_miscutl.c + * Wireshark Memory Manager Misc Utilities + * Copyright 2013, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#include +#include + +#include "wmem_core.h" +#include "wmem_miscutl.h" + +void * +wmem_memdup(wmem_allocator_t *allocator, const void *source, const size_t size) +{ + void *dest; + + if (!size) + return NULL; + + dest = wmem_alloc(allocator, size); + memcpy(dest, source, size); + + return dest; +} + +int +wmem_compare_int(gconstpointer a, gconstpointer b) +{ + return GPOINTER_TO_INT(a) - GPOINTER_TO_INT(b); +} + +int +wmem_compare_uint(gconstpointer a, gconstpointer b) +{ + return GPOINTER_TO_UINT(a) > GPOINTER_TO_UINT(b) ? 1 : (GPOINTER_TO_UINT(a) < GPOINTER_TO_UINT(b) ? -1 : 0); +} + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_miscutl.h b/wsutil/wmem/wmem_miscutl.h new file mode 100644 index 00000000..714ee5cc --- /dev/null +++ b/wsutil/wmem/wmem_miscutl.h @@ -0,0 +1,73 @@ +/** @file + * Definitions for the Wireshark Memory Manager Misc Utilities + * Copyright 2013, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#ifndef __WMEM_MISCUTL_H__ +#define __WMEM_MISCUTL_H__ + +#include +#include + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +/** @addtogroup wmem + * @{ + * @defgroup wmem-strutl String Utilities + * + * A collection of misc. utility functions for wmem. + * + * @{ + */ + +/** Copies a block of memory. + * + * @param allocator The allocator object to use to allocate memory to copy into. + * @param source The pointer to the memory block to copy. + * @param size The amount of memory to copy. + * @return The location of the memory copy or NULL if size is 0. + */ +WS_DLL_PUBLIC +void * +wmem_memdup(wmem_allocator_t *allocator, const void *source, const size_t size) +G_GNUC_MALLOC; + +/** Generic GCompareFunc implementations to compare signed/unsigned integer + */ +WS_DLL_PUBLIC +int +wmem_compare_int(gconstpointer a, gconstpointer b); + +WS_DLL_PUBLIC +int +wmem_compare_uint(gconstpointer a, gconstpointer b); + +/** @} + * @} */ + +#ifdef __cplusplus +} +#endif /* __cplusplus */ + +#endif /* __WMEM_MISCUTL_H__ */ + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_multimap.c b/wsutil/wmem/wmem_multimap.c new file mode 100644 index 00000000..b36e5ced --- /dev/null +++ b/wsutil/wmem/wmem_multimap.c @@ -0,0 +1,185 @@ +/* wmem_multimap.c + * Wireshark Memory Manager Hash Multimap + * Copyright 2021, John Thacker + * Copyright 2014, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ +#include "config.h" + +#include + +#include "wmem_core.h" +#include "wmem_list.h" +#include "wmem_map.h" +#include "wmem_multimap.h" +#include "wmem_tree.h" +#include "wmem_user_cb.h" + +struct _wmem_multimap_t { + + wmem_map_t *map; + + unsigned metadata_scope_cb_id; + unsigned data_scope_cb_id; + + wmem_allocator_t *metadata_allocator; + wmem_allocator_t *data_allocator; +}; + +wmem_multimap_t * +wmem_multimap_new(wmem_allocator_t *allocator, + GHashFunc hash_func, GEqualFunc eql_func) +{ + wmem_multimap_t *multimap; + + multimap = wmem_new(allocator, wmem_multimap_t); + + multimap->map = wmem_map_new(allocator, hash_func, eql_func); + multimap->metadata_allocator = allocator; + multimap->data_allocator = allocator; + + return multimap; +} + +static bool +wmem_multimap_reset_cb(wmem_allocator_t *allocator _U_, wmem_cb_event_t event, + void *user_data) +{ + wmem_multimap_t *multimap = (wmem_multimap_t*)user_data; + + if (event == WMEM_CB_DESTROY_EVENT) { + wmem_unregister_callback(multimap->metadata_allocator, multimap->metadata_scope_cb_id); + wmem_free(multimap->metadata_allocator, multimap); + } + + return true; +} + +static bool +wmem_multimap_destroy_cb(wmem_allocator_t *allocator _U_, wmem_cb_event_t event _U_, + void *user_data) +{ + wmem_multimap_t *multimap = (wmem_multimap_t*)user_data; + + wmem_unregister_callback(multimap->data_allocator, multimap->data_scope_cb_id); + + return false; +} + +wmem_multimap_t * +wmem_multimap_new_autoreset(wmem_allocator_t *metadata_scope, wmem_allocator_t *data_scope, + GHashFunc hash_func, GEqualFunc eql_func) +{ + wmem_multimap_t *multimap; + + multimap = wmem_new(metadata_scope, wmem_multimap_t); + + multimap->map = wmem_map_new_autoreset(metadata_scope, data_scope, hash_func, eql_func); + multimap->metadata_allocator = metadata_scope; + multimap->data_allocator = data_scope; + + multimap->metadata_scope_cb_id = wmem_register_callback(metadata_scope, wmem_multimap_destroy_cb, multimap); + multimap->data_scope_cb_id = wmem_register_callback(data_scope, wmem_multimap_reset_cb, multimap); + + return multimap; +} + +wmem_list_t* +wmem_multimap_get_keys(wmem_allocator_t *list_allocator, wmem_multimap_t *map) +{ + return wmem_map_get_keys(list_allocator, map->map); +} + +static void +count_nodes(void * key _U_, void * value, void * user_data) +{ + unsigned* count = (unsigned*)user_data; + (*count) += wmem_tree_count(value); +} + +unsigned +wmem_multimap_size(wmem_multimap_t *map) +{ + unsigned count = 0; + + wmem_map_foreach(map->map, count_nodes, &count); + return count; +} + +unsigned +wmem_multimap_count(wmem_multimap_t *map, const void *key) +{ + wmem_tree_t *tree; + + if ((tree = wmem_map_lookup(map->map, key)) == NULL) { + return 0; + } + return wmem_tree_count(tree); +} + +bool +wmem_multimap_insert32(wmem_multimap_t *map, const void *key, uint32_t frame_num, void *value) +{ + wmem_tree_t *tree; + bool ret = true; + + if ((tree = wmem_map_lookup(map->map, key)) == NULL) { + tree = wmem_tree_new(map->data_allocator); + wmem_map_insert(map->map, key, tree); + ret = false; + } + wmem_tree_insert32(tree, frame_num, value); + + return ret; +} + +void * +wmem_multimap_lookup32(wmem_multimap_t *map, const void *key, uint32_t frame_num) +{ + wmem_tree_t *tree; + + if ((tree = wmem_map_lookup(map->map, key)) == NULL) { + return NULL; + } + return wmem_tree_lookup32(tree, frame_num); +} + +void * +wmem_multimap_lookup32_le(wmem_multimap_t *map, const void *key, uint32_t frame_num) +{ + wmem_tree_t *tree; + + if ((tree = wmem_map_lookup(map->map, key)) == NULL) { + return NULL; + } + return wmem_tree_lookup32_le(tree, frame_num); +} + +void * +wmem_multimap_remove32(wmem_multimap_t *map, const void *key, const uint32_t frame_num) +{ + wmem_tree_t *tree; + + if ((tree = wmem_map_lookup(map->map, key)) == NULL) { + return NULL; + } + return wmem_tree_remove32(tree, frame_num); +} + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_multimap.h b/wsutil/wmem/wmem_multimap.h new file mode 100644 index 00000000..57f0fefb --- /dev/null +++ b/wsutil/wmem/wmem_multimap.h @@ -0,0 +1,195 @@ +/** @file + * + * Definitions for the Wireshark Memory Manager Hash Multimap + * Copyright 2021, John Thacker + * Copyright 2014, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#ifndef __WMEM_MULTIMAP_H__ +#define __WMEM_MULTIMAP_H__ + +#include + +#include "wmem_core.h" +#include "wmem_list.h" + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +/** @addtogroup wmem + * @{ + * @defgroup wmem-multimap Hash Multimap + * + * A hash multimap implementation on top of wmem_map and wmem_tree, storing + * multiple values at each hash key in a tree indexed by a 32 bit integer. + * + * The primary use case is a protocol with an ID used as the hash lookup + * key that can be reused in a capture, and the frame number used as the + * tree key. We often want to find the most recent frame that had a certain + * ID, e.g. for request/response matching, and wmem_multimap_lookup32_le() + * serves that purpose. + * + * Since the tree implementation is a self-balancing red-black tree, lookup + * time is still O(log(n)) even though elements with equivalent hash keys + * are usually added in increasing order of frame number. + * + * NOTE: The multimap does not yet support inserting items without + * specifying the tree key, because the total capacity of individual trees + * (including deleted nodes) is not tracked. + * + * @{ + */ + +typedef struct _wmem_multimap_t wmem_multimap_t; + +/** Creates a multimap with the given allocator scope. When the scope is emptied, + * the map is fully destroyed. Items stored in it will not be freed unless they + * were allocated from the same scope. + * + * @param allocator The allocator scope with which to create the map. + * @param hash_func The hash function used to place inserted keys. + * @param eql_func The equality function used to compare inserted keys. + * @return The newly-allocated map. + */ +WS_DLL_PUBLIC +wmem_multimap_t * +wmem_multimap_new(wmem_allocator_t *allocator, + GHashFunc hash_func, GEqualFunc eql_func) +G_GNUC_MALLOC; + +/** Creates a multimap with two allocator scopes. The base structure lives in the + * metadata scope, and the map data lives in the data scope. Every time free_all + * occurs in the data scope the map is transparently emptied without affecting + * the location of the base / metadata structure. + * + * WARNING: None of the map (even the part in the metadata scope) can be used + * after the data scope has been *destroyed*. + * + * The primary use for this function is to create maps that reset for each new + * capture file that is loaded. This can be done by specifying wmem_epan_scope() + * as the metadata scope and wmem_file_scope() as the data scope. + */ +WS_DLL_PUBLIC +wmem_multimap_t * +wmem_multimap_new_autoreset(wmem_allocator_t *metadata_scope, wmem_allocator_t *data_scope, + GHashFunc hash_func, GEqualFunc eql_func) +G_GNUC_MALLOC; + +/** Retrieves a list of the keys inside the multimap + * + * @param list_allocator The allocator scope for the returned list. + * @param map The multimap to extract keys from + * @return list of keys in the multimap + */ +WS_DLL_PUBLIC +wmem_list_t* +wmem_multimap_get_keys(wmem_allocator_t *list_allocator, wmem_multimap_t *map); + +/** Return the total number of elements in the multimap. + * + * @param map The multimap to use + * @return the number of elements +*/ +WS_DLL_PUBLIC +unsigned +wmem_multimap_size(wmem_multimap_t *map); + +/** Returns the number of values in the multimap with a certain hash key. + * (Note: This is the number of current elements, so this can only be used to + * safely generate unique tree keys prior to insertion if no values have been + * removed, due to how the tree implementation works.) + * + * @param map The multimap to search in. + * @param key The primary key to lookup in the map. + * @return The number of values in the tree stored at map key, or zero if no + * tree exists at that key. + */ +WS_DLL_PUBLIC +unsigned +wmem_multimap_count(wmem_multimap_t *map, const void *key); + +/** Insert a value in the multimap. + * + * @param map The multimap to insert into. + * @param key The key to insert by in the map. + * @param frame_num The key to insert by in the tree. + * @param value The value to insert. + * @return true if there was already a tree mapped at key, in which case the + * caller may safely free key. (This is not necessary if key is allocated with + * a wmem pool.) + * + * Note: as with wmem_tree, if there is already a node with the same pair + * of keys, then the existing value will simply be overwritten. This is not + * a problem if the value is wmem allocated, but if it is manually managed, + * then you must ensure that the pair is unique or do a lookup before inserting. + */ +WS_DLL_PUBLIC +bool +wmem_multimap_insert32(wmem_multimap_t *map, const void *key, uint32_t frame_num, void *value); + +/** Lookup a value in the multimap combination with an exact match. + * + * @param map The multimap to search in. + * @param key The primary key to lookup in the map. + * @param frame_num The secondary key to lookup in the tree. + * @return The value stored at the keys if any, or NULL. + */ +WS_DLL_PUBLIC +void * +wmem_multimap_lookup32(wmem_multimap_t *map, const void *key, const uint32_t frame_num); + +/** Lookup a value in the multimap with an exact match for the map key + * and the largest value less than or equal to the tree key. This is + * useful for request/response matching where IDs can be reused. + * + * @param map The multimap to search in. + * @param key The primary key to lookup in the map. + * @param frame_num The secondary key to lookup in the tree. + * @return The value stored at the primary key in the map and with the largest + * key in the tree that is less than or equal to the second key if any, or NULL. + */ +WS_DLL_PUBLIC +void * +wmem_multimap_lookup32_le(wmem_multimap_t *map, const void *key, const uint32_t frame_num); + +/** Remove a value from the multimap. If no value is stored at that key pair, + * nothing happens. As with wmem_tree, this is not really a remove, but the + * value is set to NULL so that wmem_multimap_lookup32 not will find it. + * + * @param map The multimap to remove from. + * @param key The map key of the value to remove. + * @param frame_num The tree key of the value to remove. + * @return The (removed) value stored at the key if any, or NULL. + */ +WS_DLL_PUBLIC +void * +wmem_multimap_remove32(wmem_multimap_t *map, const void *key, const uint32_t frame_num); + +/** @} + * @} */ + +#ifdef __cplusplus +} +#endif /* __cplusplus */ + +#endif /* __WMEM_MULTIMAP_H__ */ + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_queue.h b/wsutil/wmem/wmem_queue.h new file mode 100644 index 00000000..49cd3e39 --- /dev/null +++ b/wsutil/wmem/wmem_queue.h @@ -0,0 +1,70 @@ +/** @file + * + * Definitions for the Wireshark Memory Manager Queue + * Copyright 2013, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#ifndef __WMEM_QUEUE_H__ +#define __WMEM_QUEUE_H__ + +#include +#include + +#include "wmem_core.h" +#include "wmem_list.h" + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +/** @addtogroup wmem + * @{ + * @defgroup wmem-queue Queue + * + * A queue implementation on top of wmem. + * + * @{ + */ + +/* Wmem queue is implemented as a dumb wrapper over Wmem list and stack */ +typedef wmem_list_t wmem_queue_t; + +#define wmem_queue_count(X) wmem_list_count(X) + +#define wmem_queue_peek(QUEUE) wmem_stack_peek(QUEUE) + +#define wmem_queue_pop(QUEUE) wmem_stack_pop(QUEUE) + +#define wmem_queue_push(QUEUE, DATA) wmem_list_append((QUEUE), (DATA)) + +#define wmem_queue_new(ALLOCATOR) wmem_list_new(ALLOCATOR) + +#define wmem_destroy_queue(QUEUE) wmem_destroy_list(QUEUE) + +/** @} + * @} */ + +#ifdef __cplusplus +} +#endif /* __cplusplus */ + +#endif /* __WMEM_QUEUE_H__ */ + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_stack.c b/wsutil/wmem/wmem_stack.c new file mode 100644 index 00000000..5123aad1 --- /dev/null +++ b/wsutil/wmem/wmem_stack.c @@ -0,0 +1,57 @@ +/* wmem_stack.c + * Wireshark Memory Manager Stack + * Copyright 2012, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#include +#include + +#include "wmem-int.h" +#include "wmem_core.h" +#include "wmem_stack.h" +#include "wmem_list.h" + +/* Wmem stack is implemented as a simple wrapper over Wmem list */ + +void * +wmem_stack_peek(const wmem_stack_t *stack) +{ + wmem_list_frame_t *frame; + + frame = wmem_list_head(stack); + + ws_assert(frame); + + return wmem_list_frame_data(frame); +} + +void * +wmem_stack_pop(wmem_stack_t *stack) +{ + void *data; + + data = wmem_stack_peek(stack); + + wmem_list_remove(stack, data); + + return data; +} + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_stack.h b/wsutil/wmem/wmem_stack.h new file mode 100644 index 00000000..b4fd2d56 --- /dev/null +++ b/wsutil/wmem/wmem_stack.h @@ -0,0 +1,73 @@ +/** @file + * Definitions for the Wireshark Memory Manager Stack + * Copyright 2012, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#ifndef __WMEM_STACK_H__ +#define __WMEM_STACK_H__ + +#include +#include + +#include "wmem_core.h" +#include "wmem_list.h" + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +/** @addtogroup wmem + * @{ + * @defgroup wmem-stack Stack + * + * A stack implementation on top of wmem. + * + * @{ + */ + +/* Wmem stack is implemented as a simple wrapper over Wmem list */ +typedef wmem_list_t wmem_stack_t; + +#define wmem_stack_count(X) wmem_list_count(X) + +WS_DLL_PUBLIC +void * +wmem_stack_peek(const wmem_stack_t *stack); + +WS_DLL_PUBLIC +void * +wmem_stack_pop(wmem_stack_t *stack); + +#define wmem_stack_push(STACK, DATA) wmem_list_prepend((STACK), (DATA)) + +#define wmem_stack_new(ALLOCATOR) wmem_list_new(ALLOCATOR) + +#define wmem_destroy_stack(STACK) wmem_destroy_list(STACK) + +/** @} + * @} */ + +#ifdef __cplusplus +} +#endif /* __cplusplus */ + +#endif /* __WMEM_STACK_H__ */ + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_strbuf.c b/wsutil/wmem/wmem_strbuf.c new file mode 100644 index 00000000..ff49f6b8 --- /dev/null +++ b/wsutil/wmem/wmem_strbuf.c @@ -0,0 +1,470 @@ +/* wmem_strbuf.c + * Wireshark Memory Manager String Buffer + * Copyright 2012, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#include "config.h" +#include "wmem_strbuf.h" + +#include +#include + +#include "wmem-int.h" +#include "wmem_strutl.h" + +#include + +#define DEFAULT_MINIMUM_SIZE 16 + +/* _ROOM accounts for the null-terminator, _RAW_ROOM does not. + * Some functions need one, some functions need the other. */ +#define WMEM_STRBUF_ROOM(S) ((S)->alloc_size - (S)->len - 1) +#define WMEM_STRBUF_RAW_ROOM(S) ((S)->alloc_size - (S)->len) + +wmem_strbuf_t * +wmem_strbuf_new_sized(wmem_allocator_t *allocator, + size_t alloc_size) +{ + wmem_strbuf_t *strbuf; + + strbuf = wmem_new(allocator, wmem_strbuf_t); + + strbuf->allocator = allocator; + strbuf->len = 0; + strbuf->alloc_size = alloc_size ? alloc_size : DEFAULT_MINIMUM_SIZE; + + strbuf->str = (char *)wmem_alloc(strbuf->allocator, strbuf->alloc_size); + strbuf->str[0] = '\0'; + + return strbuf; +} + +wmem_strbuf_t * +wmem_strbuf_new_len(wmem_allocator_t *allocator, const char *str, size_t len) +{ + wmem_strbuf_t *strbuf; + size_t alloc_size; + + alloc_size = DEFAULT_MINIMUM_SIZE; + + /* +1 for the null-terminator */ + while (alloc_size < (len + 1)) { + alloc_size *= 2; + } + + strbuf = wmem_strbuf_new_sized(allocator, alloc_size); + + if (str && len > 0) { + ws_assert(strbuf->alloc_size >= len + 1); + memcpy(strbuf->str, str, len); + strbuf->str[len] = '\0'; + strbuf->len = len; + } + + return strbuf; +} + +wmem_strbuf_t * +wmem_strbuf_new(wmem_allocator_t *allocator, const char *str) +{ + return wmem_strbuf_new_len(allocator, str, str ? strlen(str) : 0); +} + +wmem_strbuf_t * +wmem_strbuf_dup(wmem_allocator_t *allocator, const wmem_strbuf_t *src) +{ + wmem_strbuf_t *new; + + new = wmem_strbuf_new_sized(allocator, src->alloc_size); + new->len = src->len; + memcpy(new->str, src->str, new->len); + new->str[new->len] = '\0'; + return new; +} + +/* grows the allocated size of the wmem_strbuf_t. If max_size is set, then + * not guaranteed to grow by the full amount to_add */ +static inline void +wmem_strbuf_grow(wmem_strbuf_t *strbuf, const size_t to_add) +{ + size_t new_alloc_len, new_len; + + /* short-circuit for efficiency if we have room already; greatly speeds up + * repeated calls to wmem_strbuf_append_c and others which grow a little bit + * at a time. + */ + if (WMEM_STRBUF_ROOM(strbuf) >= to_add) { + return; + } + + new_alloc_len = strbuf->alloc_size; + new_len = strbuf->len + to_add; + + /* +1 for the null-terminator */ + while (new_alloc_len < (new_len + 1)) { + new_alloc_len *= 2; + } + + if (new_alloc_len == strbuf->alloc_size) { + return; + } + + strbuf->str = (char *)wmem_realloc(strbuf->allocator, strbuf->str, new_alloc_len); + + strbuf->alloc_size = new_alloc_len; +} + +void +wmem_strbuf_append(wmem_strbuf_t *strbuf, const char *str) +{ + size_t append_len; + + if (!str || str[0] == '\0') { + return; + } + + append_len = strlen(str); + wmem_strbuf_grow(strbuf, append_len); + + ws_assert(WMEM_STRBUF_RAW_ROOM(strbuf) >= append_len + 1); + memcpy(&strbuf->str[strbuf->len], str, append_len); + strbuf->len += append_len; + strbuf->str[strbuf->len] = '\0'; +} + +void +wmem_strbuf_append_len(wmem_strbuf_t *strbuf, const char *str, size_t append_len) +{ + + if (!append_len || !str) { + return; + } + + wmem_strbuf_grow(strbuf, append_len); + + memcpy(&strbuf->str[strbuf->len], str, append_len); + strbuf->len += append_len; + strbuf->str[strbuf->len] = '\0'; +} + +static inline +int _strbuf_vsnprintf(wmem_strbuf_t *strbuf, const char *format, va_list ap) +{ + int want_len; + char *buffer = &strbuf->str[strbuf->len]; + size_t buffer_size = WMEM_STRBUF_RAW_ROOM(strbuf); + + want_len = vsnprintf(buffer, buffer_size, format, ap); + if (want_len < 0) { + /* Error. */ + g_warning("%s: vsnprintf: (%d) %s", G_STRFUNC, want_len, g_strerror(errno)); + return -1; + } + if ((size_t)want_len < buffer_size) { + /* Success. */ + strbuf->len += want_len; + return 0; + } + + /* Not enough space in buffer, output was truncated. */ + strbuf->str[strbuf->len] = '\0'; /* Reset. */ + + return want_len; /* Length (not including terminating null) that would be written + if there was enough space in buffer. */ +} + +void +wmem_strbuf_append_vprintf(wmem_strbuf_t *strbuf, const char *fmt, va_list ap) +{ + int want_len; + va_list ap2; + + va_copy(ap2, ap); + /* Try to write buffer, check if output fits. */ + want_len = _strbuf_vsnprintf(strbuf, fmt, ap2); + va_end(ap2); + if (want_len <= 0) + return; + + /* Resize buffer and try again. */ + wmem_strbuf_grow(strbuf, want_len); + want_len = _strbuf_vsnprintf(strbuf, fmt, ap); + /* Second time must succeed or error out. */ + ws_assert(want_len <= 0); +} + +void +wmem_strbuf_append_printf(wmem_strbuf_t *strbuf, const char *format, ...) +{ + va_list ap; + + va_start(ap, format); + wmem_strbuf_append_vprintf(strbuf, format, ap); + va_end(ap); +} + +void +wmem_strbuf_append_c(wmem_strbuf_t *strbuf, const char c) +{ + wmem_strbuf_grow(strbuf, 1); + + strbuf->str[strbuf->len] = c; + strbuf->len++; + strbuf->str[strbuf->len] = '\0'; +} + +void +wmem_strbuf_append_c_count(wmem_strbuf_t *strbuf, const char c, size_t count) +{ + wmem_strbuf_grow(strbuf, count); + + while (count-- > 0) { + strbuf->str[strbuf->len++] = c; + } + strbuf->str[strbuf->len] = '\0'; +} + +void +wmem_strbuf_append_unichar(wmem_strbuf_t *strbuf, const gunichar c) +{ + char buf[6]; + size_t charlen; + + charlen = g_unichar_to_utf8(c, buf); + + wmem_strbuf_grow(strbuf, charlen); + + memcpy(&strbuf->str[strbuf->len], buf, charlen); + strbuf->len += charlen; + strbuf->str[strbuf->len] = '\0'; +} + +void +wmem_strbuf_append_unichar_validated(wmem_strbuf_t *strbuf, const gunichar c) +{ + if (g_unichar_validate(c)) { + wmem_strbuf_append_unichar(strbuf, c); + } else { + wmem_strbuf_append_unichar(strbuf, UNICODE_REPLACEMENT_CHARACTER); + } +} + +static const char hex[16] = { '0', '1', '2', '3', '4', '5', '6', '7', + '8', '9', 'A', 'B', 'C', 'D', 'E', 'F' }; + +#define HEX_CODELEN 4 + +void +wmem_strbuf_append_hex(wmem_strbuf_t *strbuf, uint8_t ch) +{ + wmem_strbuf_grow(strbuf, HEX_CODELEN * 1); + + strbuf->str[strbuf->len++] = '\\'; + strbuf->str[strbuf->len++] = 'x'; + strbuf->str[strbuf->len++] = hex[(ch >> 4) & 0xF]; + strbuf->str[strbuf->len++] = hex[(ch >> 0) & 0xF]; + strbuf->str[strbuf->len] = '\0'; +} + +#define BMP_CODELEN 6 + +static inline +void append_hex_bmp(wmem_strbuf_t *strbuf, gunichar ch) +{ + wmem_strbuf_grow(strbuf, BMP_CODELEN * 1); + + strbuf->str[strbuf->len++] = '\\'; + strbuf->str[strbuf->len++] = 'u'; + strbuf->str[strbuf->len++] = hex[(ch >> 12) & 0xF]; + strbuf->str[strbuf->len++] = hex[(ch >> 8) & 0xF]; + strbuf->str[strbuf->len++] = hex[(ch >> 4) & 0xF]; + strbuf->str[strbuf->len++] = hex[(ch >> 0) & 0xF]; + strbuf->str[strbuf->len] = '\0'; +} + +#define ANY_CODELEN 10 + +static inline +void append_hex_any(wmem_strbuf_t *strbuf, gunichar ch) +{ + wmem_strbuf_grow(strbuf, ANY_CODELEN * 1); + + strbuf->str[strbuf->len++] = '\\'; + strbuf->str[strbuf->len++] = 'U'; + strbuf->str[strbuf->len++] = hex[(ch >> 28) & 0xF]; + strbuf->str[strbuf->len++] = hex[(ch >> 24) & 0xF]; + strbuf->str[strbuf->len++] = hex[(ch >> 20) & 0xF]; + strbuf->str[strbuf->len++] = hex[(ch >> 16) & 0xF]; + strbuf->str[strbuf->len++] = hex[(ch >> 12) & 0xF]; + strbuf->str[strbuf->len++] = hex[(ch >> 8) & 0xF]; + strbuf->str[strbuf->len++] = hex[(ch >> 4) & 0xF]; + strbuf->str[strbuf->len++] = hex[(ch >> 0) & 0xF]; + strbuf->str[strbuf->len] = '\0'; +} + +size_t +wmem_strbuf_append_hex_unichar(wmem_strbuf_t *strbuf, gunichar ch) +{ + if (ch <= 0x7f) { + wmem_strbuf_append_hex(strbuf, (uint8_t)ch); + return HEX_CODELEN; + } + if (ch <= 0xffff) { + append_hex_bmp(strbuf, ch); + return BMP_CODELEN; + } + append_hex_any(strbuf, ch); + return ANY_CODELEN; +} + +void +wmem_strbuf_truncate(wmem_strbuf_t *strbuf, const size_t len) +{ + if (len >= strbuf->len) { + return; + } + + strbuf->str[len] = '\0'; + strbuf->len = len; +} + +const char * +wmem_strbuf_get_str(const wmem_strbuf_t *strbuf) +{ + return strbuf->str; +} + +size_t +wmem_strbuf_get_len(const wmem_strbuf_t *strbuf) +{ + return strbuf->len; +} + +static inline int +_memcmp_len(const void *s1, size_t s1_len, const void *s2, size_t s2_len) +{ + size_t len; + int cmp; + + len = MIN(s1_len, s2_len); + if ((cmp = memcmp(s1, s2, len)) != 0) + return cmp; + if (s1_len < s2_len) + return -1; + if (s1_len > s2_len) + return 1; + return 0; +} + +WS_DLL_PUBLIC +int +wmem_strbuf_strcmp(const wmem_strbuf_t *sb1, const wmem_strbuf_t *sb2) +{ + return _memcmp_len(sb1->str, sb1->len, sb2->str, sb2->len); +} + +const char * +wmem_strbuf_strstr(const wmem_strbuf_t *haystack, const wmem_strbuf_t *needle) +{ + return ws_memmem(haystack->str, haystack->len, needle->str, needle->len); +} + +/* Truncates the allocated memory down to the minimal amount, frees the header + * structure, and returns a non-const pointer to the raw string. The + * wmem_strbuf_t structure cannot be used after this is called. + */ +char * +wmem_strbuf_finalize(wmem_strbuf_t *strbuf) +{ + if (strbuf == NULL) + return NULL; + + char *ret = (char *)wmem_realloc(strbuf->allocator, strbuf->str, strbuf->len+1); + + wmem_free(strbuf->allocator, strbuf); + + return ret; +} + +void +wmem_strbuf_destroy(wmem_strbuf_t *strbuf) +{ + if (strbuf == NULL) + return; + + wmem_free(strbuf->allocator, strbuf->str); + wmem_free(strbuf->allocator, strbuf); +} + +static bool +string_utf8_validate(const char *str, ssize_t max_len, const char **endpptr) +{ + bool valid; + const char *endp; + + if (max_len <= 0) { + if (endpptr) { + *endpptr = str; + } + return true; + } + + valid = g_utf8_validate(str, max_len, &endp); + + if (valid || *endp != '\0') { + if (endpptr) { + *endpptr = endp; + } + return valid; + } + + /* Invalid because of a nul byte. Skip nuls and continue. */ + max_len -= endp - str; + str = endp; + while (max_len > 0 && *str == '\0') { + str++; + max_len--; + } + return string_utf8_validate(str, max_len, endpptr); +} + +/* g_utf8_validate() returns false in the string contains embedded NUL + * bytes. We accept \x00 as valid and work around that to validate the + * entire len bytes. */ +bool +wmem_strbuf_utf8_validate(wmem_strbuf_t *strbuf, const char **endpptr) +{ + return string_utf8_validate(strbuf->str, strbuf->len, endpptr); +} + +void +wmem_strbuf_utf8_make_valid(wmem_strbuf_t *strbuf) +{ + wmem_strbuf_t *tmp = ws_utf8_make_valid_strbuf(strbuf->allocator, strbuf->str, strbuf->len); + + wmem_free(strbuf->allocator, strbuf->str); + strbuf->str = tmp->str; + strbuf->len = tmp->len; + strbuf->alloc_size = tmp->alloc_size; + + wmem_free(strbuf->allocator, tmp); +} + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_strbuf.h b/wsutil/wmem/wmem_strbuf.h new file mode 100644 index 00000000..9c00b6e4 --- /dev/null +++ b/wsutil/wmem/wmem_strbuf.h @@ -0,0 +1,194 @@ +/** @file + * Definitions for the Wireshark Memory Manager String Buffer + * Copyright 2012, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#ifndef __WMEM_STRBUF_H__ +#define __WMEM_STRBUF_H__ + +#include + +#include "wmem_core.h" + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +/** @addtogroup wmem + * @{ + * @defgroup wmem-strbuf String Buffer + * + * A string object implementation on top of wmem. + * + * @{ + */ + +/* Holds a wmem-allocated string-buffer. + * len is the length of the string (not counting the null-terminator) and + * should be the same as strlen(str) unless the string contains embedded + * nulls. + * alloc_size is the size of the raw buffer pointed to by str, regardless of + * what string is actually being stored (i.e. the buffer contents) + * max_size is the maximum permitted alloc_size (NOT the maximum permitted len, + * which must be one shorter than alloc_size to permit null-termination). + * When max_size is 0 (the default), no maximum is enforced. + */ +struct _wmem_strbuf_t { + /* read-only fields */ + wmem_allocator_t *allocator; + char *str; + size_t len; + + /* private fields */ + size_t alloc_size; +}; + +typedef struct _wmem_strbuf_t wmem_strbuf_t; + +WS_DLL_PUBLIC +wmem_strbuf_t * +wmem_strbuf_new_sized(wmem_allocator_t *allocator, size_t alloc_size) +G_GNUC_MALLOC; + +WS_DLL_PUBLIC +wmem_strbuf_t * +wmem_strbuf_new(wmem_allocator_t *allocator, const char *str) +G_GNUC_MALLOC; + +#define wmem_strbuf_create(allocator) \ + wmem_strbuf_new(allocator, "") + +WS_DLL_PUBLIC +wmem_strbuf_t * +wmem_strbuf_new_len(wmem_allocator_t *allocator, const char *str, size_t len) +G_GNUC_MALLOC; + +WS_DLL_PUBLIC +wmem_strbuf_t * +wmem_strbuf_dup(wmem_allocator_t *allocator, const wmem_strbuf_t *strbuf) +G_GNUC_MALLOC; + +WS_DLL_PUBLIC +void +wmem_strbuf_append(wmem_strbuf_t *strbuf, const char *str); + +/* Appends up to append_len bytes (as allowed by strbuf->max_size) from + * str. Ensures that strbuf is null terminated afterwards but will copy + * embedded nulls. */ +WS_DLL_PUBLIC +void +wmem_strbuf_append_len(wmem_strbuf_t *strbuf, const char *str, size_t append_len); + +WS_DLL_PUBLIC +void +wmem_strbuf_append_printf(wmem_strbuf_t *strbuf, const char *format, ...) +G_GNUC_PRINTF(2, 3); + +WS_DLL_PUBLIC +void +wmem_strbuf_append_vprintf(wmem_strbuf_t *strbuf, const char *fmt, va_list ap); + +WS_DLL_PUBLIC +void +wmem_strbuf_append_c(wmem_strbuf_t *strbuf, const char c); + +WS_DLL_PUBLIC +void +wmem_strbuf_append_c_count(wmem_strbuf_t *strbuf, const char c, size_t count); + +WS_DLL_PUBLIC +void +wmem_strbuf_append_unichar(wmem_strbuf_t *strbuf, const gunichar c); + +#define wmem_strbuf_append_unichar_repl(buf) \ + wmem_strbuf_append_unichar(buf, UNICODE_REPLACEMENT_CHARACTER) + +/* As wmem_strbuf_append_unichar but appends a REPLACEMENT CHARACTER + * instead for any invalid Unicode codepoints. + */ +WS_DLL_PUBLIC +void +wmem_strbuf_append_unichar_validated(wmem_strbuf_t *strbuf, const gunichar c); + +WS_DLL_PUBLIC +void +wmem_strbuf_append_hex(wmem_strbuf_t *strbuf, uint8_t); + +/* Returns the number of characters written (4, 6 or 10). */ +WS_DLL_PUBLIC +size_t +wmem_strbuf_append_hex_unichar(wmem_strbuf_t *strbuf, gunichar); + +WS_DLL_PUBLIC +void +wmem_strbuf_truncate(wmem_strbuf_t *strbuf, const size_t len); + +WS_DLL_PUBLIC +const char * +wmem_strbuf_get_str(const wmem_strbuf_t *strbuf); + +WS_DLL_PUBLIC +size_t +wmem_strbuf_get_len(const wmem_strbuf_t *strbuf); + +WS_DLL_PUBLIC +int +wmem_strbuf_strcmp(const wmem_strbuf_t *sb1, const wmem_strbuf_t *sb2); + +WS_DLL_PUBLIC +const char * +wmem_strbuf_strstr(const wmem_strbuf_t *haystack, const wmem_strbuf_t *needle); + +/** Truncates the allocated memory down to the minimal amount, frees the header + * structure, and returns a non-const pointer to the raw string. The + * wmem_strbuf_t structure cannot be used after this is called. Basically a + * destructor for when you still need the underlying C-string. + */ +WS_DLL_PUBLIC +char * +wmem_strbuf_finalize(wmem_strbuf_t *strbuf); + +WS_DLL_PUBLIC +void +wmem_strbuf_destroy(wmem_strbuf_t *strbuf); + +/* Validates the string buffer as UTF-8. + * Unlike g_utf8_validate(), accepts embedded NUL bytes as valid UTF-8. + * If endpptr is non-NULL, then the end of the valid range is stored there + * (i.e. the first invalid character, or the end of the buffer otherwise). + */ +WS_DLL_PUBLIC +bool +wmem_strbuf_utf8_validate(wmem_strbuf_t *strbuf, const char **endptr); + +WS_DLL_PUBLIC +void +wmem_strbuf_utf8_make_valid(wmem_strbuf_t *strbuf); + +/** @} + * @} */ + +#ifdef __cplusplus +} +#endif /* __cplusplus */ + +#endif /* __WMEM_STRBUF_H__ */ + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_strutl.c b/wsutil/wmem/wmem_strutl.c new file mode 100644 index 00000000..99f1f8c6 --- /dev/null +++ b/wsutil/wmem/wmem_strutl.c @@ -0,0 +1,159 @@ +/* wmem_strutl.c + * Wireshark Memory Manager String Utilities + * Copyright 2012, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ +#define _GNU_SOURCE +#include "config.h" +#include "wmem_strutl.h" + +#include +#include +#include + +char * +wmem_strdup(wmem_allocator_t *allocator, const char *src) +{ + size_t len; + + /* If the string is NULL, just return the string "" so that the + * callers don't have to bother checking it. */ + if (!src) { + src = ""; + } + + len = strlen(src) + 1; /* +1 for the null-terminator */ + + return (char *)memcpy(wmem_alloc(allocator, len), src, len); +} + +char * +wmem_strndup(wmem_allocator_t *allocator, const char *src, const size_t len) +{ + char *dst; + unsigned i; + + dst = (char *)wmem_alloc(allocator, len+1); + + for (i=0; (i < len) && src[i]; i++) { + dst[i] = src[i]; + } + + dst[i] = '\0'; + + return dst; +} + +char * +wmem_strdup_printf(wmem_allocator_t *allocator, const char *fmt, ...) +{ + va_list ap; + char *dst; + + va_start(ap, fmt); + dst = wmem_strdup_vprintf(allocator, fmt, ap); + va_end(ap); + + return dst; +} + +#ifdef HAVE_VASPRINTF +static char * +_strdup_vasprintf(const char *fmt, va_list ap) +{ + char *str = NULL; + int ret; + + ret = vasprintf(&str, fmt, ap); + if (ret == -1 && errno == ENOMEM) { + /* Out of memory. We have to mimic GLib here and abort. */ + g_error("%s: failed to allocate memory", G_STRLOC); + } + return str; +} +#endif /* HAVE_VASPRINTF */ + +#define WMEM_STRDUP_VPRINTF_DEFAULT_BUFFER 256 +char * +wmem_strdup_vprintf(wmem_allocator_t *allocator, const char *fmt, va_list ap) +{ + va_list ap2; + char buf[WMEM_STRDUP_VPRINTF_DEFAULT_BUFFER]; + int needed_len; + char *new_buf; + size_t new_buf_size; + +#ifdef HAVE_VASPRINTF + if (allocator == NULL) { + return _strdup_vasprintf(fmt, ap); + } +#endif + + va_copy(ap2, ap); + needed_len = vsnprintf(buf, sizeof(buf), fmt, ap2); + va_end(ap2); + + new_buf_size = needed_len + 1; + new_buf = wmem_alloc(allocator, new_buf_size); + + if (new_buf_size <= WMEM_STRDUP_VPRINTF_DEFAULT_BUFFER) { + memcpy(new_buf, buf, new_buf_size); + return new_buf; + } + vsnprintf(new_buf, new_buf_size, fmt, ap); + return new_buf; +} + +/* Return the first occurrence of needle in haystack. + * If not found, return NULL. + * If either haystack or needle has 0 length, return NULL.*/ +const uint8_t * +ws_memmem(const void *_haystack, size_t haystack_len, + const void *_needle, size_t needle_len) +{ +#ifdef HAVE_MEMMEM + return memmem(_haystack, haystack_len, _needle, needle_len); +#else + /* Algorithm copied from GNU's glibc 2.3.2 memmem() under LGPL 2.1+ */ + const uint8_t *haystack = _haystack; + const uint8_t *needle = _needle; + const uint8_t *begin; + const uint8_t *const last_possible = haystack + haystack_len - needle_len; + + if (needle_len == 0) { + return NULL; + } + + if (needle_len > haystack_len) { + return NULL; + } + + for (begin = haystack ; begin <= last_possible; ++begin) { + if (begin[0] == needle[0] && + !memcmp(&begin[1], needle + 1, + needle_len - 1)) { + return begin; + } + } + + return NULL; +#endif /* HAVE_MEMMEM */ +} + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_strutl.h b/wsutil/wmem/wmem_strutl.h new file mode 100644 index 00000000..ee3aed65 --- /dev/null +++ b/wsutil/wmem/wmem_strutl.h @@ -0,0 +1,95 @@ +/** @file + * Definitions for the Wireshark Memory Manager String Utilities + * Copyright 2012, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#ifndef __WMEM_STRUTL_H__ +#define __WMEM_STRUTL_H__ + +#include + +#include "wmem_core.h" + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +/** @addtogroup wmem + * @{ + * @defgroup wmem-strutl String Utilities + * + * A collection of utility function for operating on C strings with wmem. + * + * @{ + */ + +WS_DLL_PUBLIC +char * +wmem_strdup(wmem_allocator_t *allocator, const char *src) +G_GNUC_MALLOC; + +#define ws_strdup(src) wmem_strdup(NULL, src) + +WS_DLL_PUBLIC +char * +wmem_strndup(wmem_allocator_t *allocator, const char *src, const size_t len) +G_GNUC_MALLOC; + +#define ws_strndup(src, len) wmem_strndup(NULL, src, len) + +WS_DLL_PUBLIC +char * +wmem_strdup_printf(wmem_allocator_t *allocator, const char *fmt, ...) +G_GNUC_MALLOC G_GNUC_PRINTF(2, 3); + +#define ws_strdup_printf(...) wmem_strdup_printf(NULL, __VA_ARGS__) + +WS_DLL_PUBLIC +char * +wmem_strdup_vprintf(wmem_allocator_t *allocator, const char *fmt, va_list ap) +G_GNUC_MALLOC; + +#define ws_strdup_vprintf(fmt, ap) wmem_strdup_vprintf(NULL, fmt, ap) + +/** + * Return the first occurrence of needle in haystack. + * + * @param haystack The data to search + * @param haystack_len The length of the search data + * @param needle The string to look for + * @param needle_len The length of the search string + * @return A pointer to the first occurrence of "needle" in + * "haystack". If "needle" isn't found or is NULL, or if + * "needle_len" is 0, NULL is returned. + */ +WS_DLL_PUBLIC +const uint8_t *ws_memmem(const void *haystack, size_t haystack_len, + const void *needle, size_t needle_len); + +/** @} + * @} */ + +#ifdef __cplusplus +} +#endif /* __cplusplus */ + +#endif /* __WMEM_STRUTL_H__ */ + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_test.c b/wsutil/wmem/wmem_test.c new file mode 100644 index 00000000..0dc908b7 --- /dev/null +++ b/wsutil/wmem/wmem_test.c @@ -0,0 +1,1496 @@ +/* wmem_test.c + * Wireshark Memory Manager Tests + * Copyright 2012, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#include "config.h" + +#include +#include + +#include "wmem.h" +#include "wmem_tree-int.h" +#include "wmem_allocator.h" +#include "wmem_allocator_block.h" +#include "wmem_allocator_block_fast.h" +#include "wmem_allocator_simple.h" +#include "wmem_allocator_strict.h" + +#include + +#define STRING_80 "12345678901234567890123456789012345678901234567890123456789012345678901234567890" +#define MAX_ALLOC_SIZE (1024*64) +#define MAX_SIMULTANEOUS_ALLOCS 1024 +#define CONTAINER_ITERS 10000 + +typedef void (*wmem_verify_func)(wmem_allocator_t *allocator); + +/* A local copy of wmem_allocator_new that ignores the + * WIRESHARK_DEBUG_WMEM_OVERRIDE variable so that test functions are + * guaranteed to actually get the allocator type they asked for */ +static wmem_allocator_t * +wmem_allocator_force_new(const wmem_allocator_type_t type) +{ + wmem_allocator_t *allocator; + + allocator = wmem_new(NULL, wmem_allocator_t); + allocator->type = type; + allocator->callbacks = NULL; + allocator->in_scope = true; + + switch (type) { + case WMEM_ALLOCATOR_SIMPLE: + wmem_simple_allocator_init(allocator); + break; + case WMEM_ALLOCATOR_BLOCK: + wmem_block_allocator_init(allocator); + break; + case WMEM_ALLOCATOR_BLOCK_FAST: + wmem_block_fast_allocator_init(allocator); + break; + case WMEM_ALLOCATOR_STRICT: + wmem_strict_allocator_init(allocator); + break; + default: + g_assert_not_reached(); + /* This is necessary to squelch MSVC errors; is there + any way to tell it that g_assert_not_reached() + never returns? */ + return NULL; + }; + + return allocator; +} + +/* A helper for generating pseudo-random strings. Just uses glib's random number + * functions to generate 'numbers' in the printable character range. */ +static char * +wmem_test_rand_string(wmem_allocator_t *allocator, int minlen, int maxlen) +{ + char *str; + int len, i; + + len = g_random_int_range(minlen, maxlen); + + /* +1 for null-terminator */ + str = (char*)wmem_alloc(allocator, len + 1); + str[len] = '\0'; + + for (i=0; i=0; i--) { + /* no wmem_realloc0 so just use memset manually */ + ptrs[i] = (char *)wmem_realloc(allocator, ptrs[i], 4*len); + memset(ptrs[i], 0, 4*len); + } + for (i=0; i, orig_str); + wmem_strict_check_canaries(allocator); + + orig_str = "TEST123456789"; + new_str = wmem_strndup(allocator, orig_str, 6); + g_assert_cmpstr(new_str, ==, "TEST12"); + g_assert_cmpstr(new_str, <, orig_str); + new_str[0] = 'X'; + g_assert_cmpstr(new_str, >, orig_str); + wmem_strict_check_canaries(allocator); + + new_str = wmem_strdup_printf(allocator, "abc %s %% %d", "boo", 23); + g_assert_cmpstr(new_str, ==, "abc boo % 23"); + new_str = wmem_strdup_printf(allocator, "%s", STRING_80); + g_assert_cmpstr(new_str, ==, STRING_80); + wmem_strict_check_canaries(allocator); + + orig_str = "Short String"; + new_str = wmem_strdup_printf(allocator, "TEST %s", orig_str); + g_assert_cmpstr(new_str, ==, "TEST Short String"); + + orig_str = "Very Long..............................." + "........................................" + "........................................" + "........................................" + "........................................" + "........................................" + "..................................String"; + new_str = wmem_strdup_printf(allocator, "TEST %s", orig_str); + g_assert_cmpstr(new_str, ==, + "TEST Very Long..............................." + "........................................" + "........................................" + "........................................" + "........................................" + "........................................" + "..................................String"); + + wmem_destroy_allocator(allocator); +} + +#define RESOURCE_USAGE_START get_resource_usage(&start_utime, &start_stime) + +#define RESOURCE_USAGE_END \ + get_resource_usage(&end_utime, &end_stime); \ + utime_ms = (end_utime - start_utime) * 1000.0; \ + stime_ms = (end_stime - start_stime) * 1000.0 + +/* NOTE: You have to run "wmem_test -m perf" to run the performance tests. */ +static void +wmem_test_stringperf(void) +{ +#define LOOP_COUNT (1 * 1000 * 1000) + wmem_allocator_t *allocator; +#ifdef _WIN32 + char buffer[1]; +#endif + char **str_ptr = g_new(char *, LOOP_COUNT); + char *s_val = "test string"; + double d_val = 1000.2; + unsigned u_val = 54321; + int i_val = -12345; + int i; + double start_utime, start_stime, end_utime, end_stime, utime_ms, stime_ms; + + allocator = wmem_allocator_new(WMEM_ALLOCATOR_BLOCK); + +/* C99 snprintf */ + + RESOURCE_USAGE_START; + for (i = 0; i < LOOP_COUNT; i++) { + snprintf(NULL, 0, "%s", s_val); + } + RESOURCE_USAGE_END; + g_test_minimized_result(utime_ms + stime_ms, + "snprintf 1 string: u %.3f ms s %.3f ms", utime_ms, stime_ms); + + RESOURCE_USAGE_START; + for (i = 0; i < LOOP_COUNT; i++) { + snprintf(NULL, 0, "%s%s%s%s%s", s_val, s_val, s_val, s_val, s_val); + } + RESOURCE_USAGE_END; + g_test_minimized_result(utime_ms + stime_ms, + "snprintf 5 strings: u %.3f ms s %.3f ms", utime_ms, stime_ms); + + RESOURCE_USAGE_START; + for (i = 0; i < LOOP_COUNT; i++) { + snprintf(NULL, 0, "%s%u%3.5f%02d", s_val, u_val, d_val, i_val); + } + RESOURCE_USAGE_END; + g_test_minimized_result(utime_ms + stime_ms, + "snprintf mixed args: u %.3f ms s %.3f ms", utime_ms, stime_ms); + +/* GLib g_snprintf (can use C99 or Gnulib) */ + + RESOURCE_USAGE_START; + for (i = 0; i < LOOP_COUNT; i++) { + g_snprintf(NULL, 0, "%s", s_val); + } + RESOURCE_USAGE_END; + g_test_minimized_result(utime_ms + stime_ms, + "g_printf_string_upper_bound (via g_snprintf) 1 string: u %.3f ms s %.3f ms", utime_ms, stime_ms); + + RESOURCE_USAGE_START; + for (i = 0; i < LOOP_COUNT; i++) { + g_snprintf(NULL, 0, "%s%s%s%s%s", s_val, s_val, s_val, s_val, s_val); + } + RESOURCE_USAGE_END; + g_test_minimized_result(utime_ms + stime_ms, + "g_printf_string_upper_bound (via g_snprintf) 5 strings: u %.3f ms s %.3f ms", utime_ms, stime_ms); + + RESOURCE_USAGE_START; + for (i = 0; i < LOOP_COUNT; i++) { + g_snprintf(NULL, 0, "%s%u%3.5f%02d", s_val, u_val, d_val, i_val); + } + RESOURCE_USAGE_END; + g_test_minimized_result(utime_ms + stime_ms, + "g_printf_string_upper_bound (via g_snprintf) mixed args: u %.3f ms s %.3f ms", utime_ms, stime_ms); + +/* Windows _snprintf_s */ + +#ifdef _WIN32 + RESOURCE_USAGE_START; + for (i = 0; i < LOOP_COUNT; i++) { + _snprintf_s(buffer, 1, _TRUNCATE, "%s", s_val); + } + RESOURCE_USAGE_END; + g_test_minimized_result(utime_ms + stime_ms, + "_snprintf_s upper bound 1 string: u %.3f ms s %.3f ms", utime_ms, stime_ms); + + RESOURCE_USAGE_START; + for (i = 0; i < LOOP_COUNT; i++) { + _snprintf_s(buffer, 1, _TRUNCATE, "%s%s%s%s%s", s_val, s_val, s_val, s_val, s_val); + } + RESOURCE_USAGE_END; + g_test_minimized_result(utime_ms + stime_ms, + "_snprintf_s upper bound 5 strings: u %.3f ms s %.3f ms", utime_ms, stime_ms); + + RESOURCE_USAGE_START; + for (i = 0; i < LOOP_COUNT; i++) { + _snprintf_s(buffer, 1, _TRUNCATE, "%s%u%3.5f%02d", s_val, u_val, d_val, i_val); + } + RESOURCE_USAGE_END; + g_test_minimized_result(utime_ms + stime_ms, + "_snprintf_s upper bound mixed args: u %.3f ms s %.3f ms", utime_ms, stime_ms); +#endif + +/* GLib strdup */ + + RESOURCE_USAGE_START; + for (i = 0; i < LOOP_COUNT; i++) { + str_ptr[i] = g_strdup_printf("%s%s", s_val, s_val); + } + RESOURCE_USAGE_END; + g_test_minimized_result(utime_ms + stime_ms, + "g_strdup_printf 2 strings: u %.3f ms s %.3f ms", utime_ms, stime_ms); + for (i = 0; i < LOOP_COUNT; i++) { + g_free(str_ptr[i]); + } + + RESOURCE_USAGE_START; + for (i = 0; i < LOOP_COUNT; i++) { + str_ptr[i] = g_strdup_printf("%s%s%s%s%s", s_val, s_val, s_val, s_val, s_val); + } + RESOURCE_USAGE_END; + g_test_minimized_result(utime_ms + stime_ms, + "g_strdup_printf 5 strings: u %.3f ms s %.3f ms", utime_ms, stime_ms); + for (i = 0; i < LOOP_COUNT; i++) { + g_free(str_ptr[i]); + } + +/* wmem strdup null allocator */ + + RESOURCE_USAGE_START; + for (i = 0; i < LOOP_COUNT; i++) { + str_ptr[i] = wmem_strdup_printf(NULL, "%s%s", s_val, s_val); + } + RESOURCE_USAGE_END; + g_test_minimized_result(utime_ms + stime_ms, + "wmem_strdup_printf() 2 strings: u %.3f ms s %.3f ms", utime_ms, stime_ms); + for (i = 0; i < LOOP_COUNT; i++) { + g_free(str_ptr[i]); + } + + RESOURCE_USAGE_START; + for (i = 0; i < LOOP_COUNT; i++) { + str_ptr[i] = wmem_strdup_printf(NULL, "%s%s%s%s%s", s_val, s_val, s_val, s_val, s_val); + } + RESOURCE_USAGE_END; + g_test_minimized_result(utime_ms + stime_ms, + "wmem_strdup_printf(NULL) 5 strings: u %.3f ms s %.3f ms", utime_ms, stime_ms); + for (i = 0; i < LOOP_COUNT; i++) { + g_free(str_ptr[i]); + } + +/* wmem strdup strict allocator */ + + RESOURCE_USAGE_START; + for (i = 0; i < LOOP_COUNT; i++) { + wmem_strdup_printf(allocator, "%s%s", s_val, s_val); + } + RESOURCE_USAGE_END; + g_test_minimized_result(utime_ms + stime_ms, + "wmem_strdup_printf(allocator) 2 strings: u %.3f ms s %.3f ms", utime_ms, stime_ms); + + RESOURCE_USAGE_START; + for (i = 0; i < LOOP_COUNT; i++) { + wmem_strdup_printf(allocator, "%s%s%s%s%s", s_val, s_val, s_val, s_val, s_val); + } + RESOURCE_USAGE_END; + g_test_minimized_result(utime_ms + stime_ms, + "wmem_strdup_printf(allocator) 5 strings: u %.3f ms s %.3f ms", utime_ms, stime_ms); + + wmem_destroy_allocator(allocator); + g_free(str_ptr); +} + +/* DATA STRUCTURE TESTING FUNCTIONS (/wmem/datastruct/) */ + +static void +wmem_test_array(void) +{ + wmem_allocator_t *allocator; + wmem_array_t *array; + unsigned int i, j, k; + uint32_t val, *buf; + uint32_t vals[8]; + uint32_t *raw; + uint32_t lastint; + + allocator = wmem_allocator_new(WMEM_ALLOCATOR_STRICT); + + array = wmem_array_new(allocator, sizeof(uint32_t)); + g_assert_true(array); + g_assert_true(wmem_array_get_count(array) == 0); + + for (i=0; i 1) { + wmem_list_remove(list, GINT_TO_POINTER(i)); + i--; + } + wmem_list_remove(list, GINT_TO_POINTER(CONTAINER_ITERS - 1)); + g_assert_true(wmem_list_count(list) == 0); + g_assert_true(wmem_list_head(list) == NULL); + g_assert_true(wmem_list_tail(list) == NULL); + + for (i=0; i0; i--) { + g_assert_true(wmem_stack_peek(stack) == GINT_TO_POINTER(i-1)); + g_assert_true(wmem_stack_pop(stack) == GINT_TO_POINTER(i-1)); + g_assert_true(wmem_stack_count(stack) == i-1); + } + g_assert_true(wmem_stack_count(stack) == 0); + + wmem_destroy_stack(stack); + + wmem_destroy_allocator(allocator); +} + +static void +wmem_test_strbuf(void) +{ + wmem_allocator_t *allocator; + wmem_strbuf_t *strbuf; + int i; + + allocator = wmem_allocator_new(WMEM_ALLOCATOR_STRICT); + + strbuf = wmem_strbuf_new(allocator, "TEST"); + g_assert_true(strbuf); + g_assert_cmpstr(wmem_strbuf_get_str(strbuf), ==, "TEST"); + g_assert_cmpuint(wmem_strbuf_get_len(strbuf), ==, 4); + + wmem_strbuf_append(strbuf, "FUZZ"); + g_assert_cmpstr(wmem_strbuf_get_str(strbuf), ==, "TESTFUZZ"); + g_assert_cmpuint(wmem_strbuf_get_len(strbuf), ==, 8); + + wmem_strbuf_append_printf(strbuf, "%d%s", 3, "a"); + g_assert_cmpstr(wmem_strbuf_get_str(strbuf), ==, "TESTFUZZ3a"); + g_assert_cmpuint(wmem_strbuf_get_len(strbuf), ==, 10); + + wmem_strbuf_append_c(strbuf, 'q'); + g_assert_cmpstr(wmem_strbuf_get_str(strbuf), ==, "TESTFUZZ3aq"); + g_assert_cmpuint(wmem_strbuf_get_len(strbuf), ==, 11); + + wmem_strbuf_append_unichar(strbuf, g_utf8_get_char("\xC2\xA9")); + g_assert_cmpstr(wmem_strbuf_get_str(strbuf), ==, "TESTFUZZ3aq\xC2\xA9"); + g_assert_cmpuint(wmem_strbuf_get_len(strbuf), ==, 13); + + wmem_strbuf_append_c_count(strbuf, '+', 8); + g_assert_cmpstr(wmem_strbuf_get_str(strbuf), ==, "TESTFUZZ3aq\xC2\xA9++++++++"); + g_assert_cmpuint(wmem_strbuf_get_len(strbuf), ==, 21); + + wmem_strbuf_truncate(strbuf, 32); + wmem_strbuf_truncate(strbuf, 24); + wmem_strbuf_truncate(strbuf, 16); + wmem_strbuf_truncate(strbuf, 13); + g_assert_cmpstr(wmem_strbuf_get_str(strbuf), ==, "TESTFUZZ3aq\xC2\xA9"); + g_assert_cmpuint(wmem_strbuf_get_len(strbuf), ==, 13); + + wmem_strbuf_truncate(strbuf, 3); + g_assert_cmpstr(wmem_strbuf_get_str(strbuf), ==, "TES"); + g_assert_cmpuint(wmem_strbuf_get_len(strbuf), ==, 3); + + wmem_strbuf_append_len(strbuf, "TFUZZ1234", 5); + g_assert_cmpstr(wmem_strbuf_get_str(strbuf), ==, "TESTFUZZ"); + g_assert_cmpuint(wmem_strbuf_get_len(strbuf), ==, 8); + + wmem_free_all(allocator); + + strbuf = wmem_strbuf_new(allocator, "TEST"); + for (i=0; i<1024; i++) { + if (g_test_rand_bit()) { + wmem_strbuf_append(strbuf, "ABC"); + } + else { + wmem_strbuf_append_printf(strbuf, "%d%d", 3, 777); + } + wmem_strict_check_canaries(allocator); + } + g_assert_true(strlen(wmem_strbuf_get_str(strbuf)) == + wmem_strbuf_get_len(strbuf)); + + wmem_destroy_allocator(allocator); +} + +static void +wmem_test_strbuf_validate(void) +{ + wmem_strbuf_t *strbuf; + const char *endptr; + + strbuf = wmem_strbuf_new(NULL, "TEST\xEF ABC"); + g_assert_false(wmem_strbuf_utf8_validate(strbuf, &endptr)); + g_assert_true(endptr == &strbuf->str[4]); + wmem_strbuf_destroy(strbuf); + + strbuf = wmem_strbuf_new(NULL, NULL); + wmem_strbuf_append_len(strbuf, "TEST\x00\x00 ABC", 10); + g_assert_true(wmem_strbuf_utf8_validate(strbuf, &endptr)); + wmem_strbuf_destroy(strbuf); + + strbuf = wmem_strbuf_new(NULL, NULL); + wmem_strbuf_append_len(strbuf, "TEST\x00\xEF ABC", 10); + g_assert_false(wmem_strbuf_utf8_validate(strbuf, &endptr)); + g_assert_true(endptr == &strbuf->str[5]); + wmem_strbuf_destroy(strbuf); + + strbuf = wmem_strbuf_new(NULL, NULL); + wmem_strbuf_append_len(strbuf, "TEST\x00 ABC \x00 DEF \x00", 17); + g_assert_true(wmem_strbuf_utf8_validate(strbuf, &endptr)); + wmem_strbuf_destroy(strbuf); +} + +static void +wmem_test_tree(void) +{ + wmem_allocator_t *allocator, *extra_allocator; + wmem_tree_t *tree; + uint32_t i; + int seen_values = 0; + int j; + char *str_key; +#define WMEM_TREE_MAX_KEY_COUNT 8 +#define WMEM_TREE_MAX_KEY_LEN 4 + int key_count; + wmem_tree_key_t keys[WMEM_TREE_MAX_KEY_COUNT]; + + allocator = wmem_allocator_new(WMEM_ALLOCATOR_STRICT); + extra_allocator = wmem_allocator_new(WMEM_ALLOCATOR_STRICT); + + tree = wmem_tree_new(allocator); + g_assert_true(tree); + g_assert_true(wmem_tree_is_empty(tree)); + + /* test basic 32-bit key operations */ + for (i=0; i 0) { + g_assert_true(wmem_tree_lookup32_le(tree, i) == GINT_TO_POINTER(i-1)); + } + wmem_tree_insert32(tree, i, GINT_TO_POINTER(i)); + g_assert_true(wmem_tree_lookup32(tree, i) == GINT_TO_POINTER(i)); + g_assert_true(!wmem_tree_is_empty(tree)); + } + g_assert_true(wmem_tree_count(tree) == CONTAINER_ITERS); + wmem_free_all(allocator); + + tree = wmem_tree_new(allocator); + for (i=0; irange)) { + d->counter++; + } + + return false; +} + + +static bool +wmem_test_overlap(uint64_t low, uint64_t high, uint64_t lowbis, uint64_t highbis) +{ + wmem_range_t r1 = {low, high, 0}; + wmem_range_t r2 = {lowbis, highbis, 0}; + return wmem_itree_range_overlap(&r1, &r2); +} + +static void +wmem_test_itree(void) +{ + wmem_allocator_t *allocator, *extra_allocator; + wmem_itree_t *tree; + int i = 0; + int32_t max_rand = 0; + wmem_test_itree_user_data_t userData; + wmem_range_t range, r2; + + allocator = wmem_allocator_new(WMEM_ALLOCATOR_STRICT); + extra_allocator = wmem_allocator_new(WMEM_ALLOCATOR_STRICT); + + tree = wmem_itree_new(allocator); + g_assert_true(tree); + g_assert_true(wmem_itree_is_empty(tree)); + + wmem_free_all(allocator); + + /* make sure that wmem_test_overlap is correct (well it's no proof but...)*/ + g_assert_true(wmem_test_overlap(0, 10, 0, 4)); + g_assert_true(wmem_test_overlap(0, 10, 9, 14)); + g_assert_true(wmem_test_overlap(5, 10, 3, 8)); + g_assert_true(wmem_test_overlap(5, 10, 1, 12)); + g_assert_true(!wmem_test_overlap(0, 10, 11, 12)); + + /* Generate a reference range, then fill an itree with random ranges, + then we count greedily the number of overlapping ranges and compare + the result with the optimized result + */ + + userData.counter = 0; + + tree = wmem_itree_new(allocator); + + /* even though keys are uint64_t, we use INT32_MAX as a max because of the type returned by + g_test_rand_int_range. + */ + max_rand = INT32_MAX; + r2.max_edge = range.max_edge = 0; + range.low = g_test_rand_int_range(0, max_rand); + range.high = g_test_rand_int_range( (int32_t)range.low, (int32_t)max_rand); + userData.range = range; + + for (i=0; i + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#ifndef __WMEM_TREE_INT_H__ +#define __WMEM_TREE_INT_H__ + +#include "wmem_tree.h" + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +typedef enum _wmem_node_color_t { + WMEM_NODE_COLOR_RED, + WMEM_NODE_COLOR_BLACK +} wmem_node_color_t; + + +struct _wmem_tree_node_t { + struct _wmem_tree_node_t *parent; + struct _wmem_tree_node_t *left; + struct _wmem_tree_node_t *right; + + const void *key; + void *data; + + wmem_node_color_t color; + bool is_subtree; + bool is_removed; + + +}; + +typedef struct _wmem_tree_node_t wmem_tree_node_t; + + +typedef struct _wmem_itree_node_t wmem_itree_node_t; + +struct _wmem_tree_t { + wmem_allocator_t *metadata_allocator; + wmem_allocator_t *data_allocator; + wmem_tree_node_t *root; + unsigned metadata_scope_cb_id; + unsigned data_scope_cb_id; + + void (*post_rotation_cb)(wmem_tree_node_t *); +}; + +typedef int (*compare_func)(const void *a, const void *b); + +wmem_tree_node_t * +wmem_tree_insert(wmem_tree_t *tree, const void *key, void *data, compare_func cmp); + +typedef struct _wmem_range_t wmem_range_t; + +bool +wmem_itree_range_overlap(const wmem_range_t *r1, const wmem_range_t *r2); + +#ifdef __cplusplus +} +#endif /* __cplusplus */ + +#endif /* __WMEM_TREE__INTERNALS_H__ */ + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_tree.c b/wsutil/wmem/wmem_tree.c new file mode 100644 index 00000000..05fa638e --- /dev/null +++ b/wsutil/wmem/wmem_tree.c @@ -0,0 +1,869 @@ +/* wmem_tree.c + * Wireshark Memory Manager Red-Black Tree + * Based on the red-black tree implementation in epan/emem.* + * Copyright 2013, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#include "config.h" + +#include +#include +#include + +#include "wmem-int.h" +#include "wmem_core.h" +#include "wmem_strutl.h" +#include "wmem_tree.h" +#include "wmem_tree-int.h" +#include "wmem_user_cb.h" + + +static wmem_tree_node_t * +node_uncle(wmem_tree_node_t *node) +{ + wmem_tree_node_t *parent, *grandparent; + + parent = node->parent; + if (parent == NULL) { + return NULL; + } + + grandparent = parent->parent; + if (grandparent == NULL) { + return NULL; + } + + if (parent == grandparent->left) { + return grandparent->right; + } + else { + return grandparent->left; + } +} + +static void rb_insert_case1(wmem_tree_t *tree, wmem_tree_node_t *node); +static void rb_insert_case2(wmem_tree_t *tree, wmem_tree_node_t *node); + +static void +rotate_left(wmem_tree_t *tree, wmem_tree_node_t *node) +{ + if (node->parent) { + if (node->parent->left == node) { + node->parent->left = node->right; + } + else { + node->parent->right = node->right; + } + } + else { + tree->root = node->right; + } + + node->right->parent = node->parent; + node->parent = node->right; + node->right = node->right->left; + if (node->right) { + node->right->parent = node; + } + node->parent->left = node; + + if (tree->post_rotation_cb) { + tree->post_rotation_cb (node); + } +} + +static void +rotate_right(wmem_tree_t *tree, wmem_tree_node_t *node) +{ + if (node->parent) { + if (node->parent->left == node) { + node->parent->left = node->left; + } + else { + node->parent->right = node->left; + } + } + else { + tree->root = node->left; + } + + node->left->parent = node->parent; + node->parent = node->left; + node->left = node->left->right; + if (node->left) { + node->left->parent = node; + } + node->parent->right = node; + + + if (tree->post_rotation_cb) { + tree->post_rotation_cb (node); + } +} + +static void +rb_insert_case5(wmem_tree_t *tree, wmem_tree_node_t *node) +{ + wmem_tree_node_t *parent, *grandparent; + + parent = node->parent; + grandparent = parent->parent; + + parent->color = WMEM_NODE_COLOR_BLACK; + grandparent->color = WMEM_NODE_COLOR_RED; + + if (node == parent->left && parent == grandparent->left) { + rotate_right(tree, grandparent); + } + else { + rotate_left(tree, grandparent); + } +} + +static void +rb_insert_case4(wmem_tree_t *tree, wmem_tree_node_t *node) +{ + wmem_tree_node_t *parent, *grandparent; + + parent = node->parent; + grandparent = parent->parent; + if (!grandparent) { + return; + } + + if (node == parent->right && parent == grandparent->left) { + rotate_left(tree, parent); + node = node->left; + } + else if (node == parent->left && parent == grandparent->right) { + rotate_right(tree, parent); + node = node->right; + } + + rb_insert_case5(tree, node); +} + +static void +rb_insert_case3(wmem_tree_t *tree, wmem_tree_node_t *node) +{ + wmem_tree_node_t *parent, *grandparent, *uncle; + + uncle = node_uncle(node); + + if (uncle && uncle->color == WMEM_NODE_COLOR_RED) { + parent = node->parent; + grandparent = parent->parent; + + parent->color = WMEM_NODE_COLOR_BLACK; + uncle->color = WMEM_NODE_COLOR_BLACK; + grandparent->color = WMEM_NODE_COLOR_RED; + + rb_insert_case1(tree, grandparent); + } + else { + rb_insert_case4(tree, node); + } +} + +static void +rb_insert_case2(wmem_tree_t *tree, wmem_tree_node_t *node) +{ + /* parent is always non-NULL here */ + if (node->parent->color == WMEM_NODE_COLOR_RED) { + rb_insert_case3(tree, node); + } +} + +static void +rb_insert_case1(wmem_tree_t *tree, wmem_tree_node_t *node) +{ + wmem_tree_node_t *parent = node->parent; + + if (parent == NULL) { + node->color = WMEM_NODE_COLOR_BLACK; + } + else { + rb_insert_case2(tree, node); + } +} + +wmem_tree_t * +wmem_tree_new(wmem_allocator_t *allocator) +{ + wmem_tree_t *tree; + + tree = wmem_new0(allocator, wmem_tree_t); + tree->metadata_allocator = allocator; + tree->data_allocator = allocator; + + return tree; +} + +static bool +wmem_tree_reset_cb(wmem_allocator_t *allocator _U_, wmem_cb_event_t event, + void *user_data) +{ + wmem_tree_t *tree = (wmem_tree_t *)user_data; + + tree->root = NULL; + + if (event == WMEM_CB_DESTROY_EVENT) { + wmem_unregister_callback(tree->metadata_allocator, tree->metadata_scope_cb_id); + wmem_free(tree->metadata_allocator, tree); + } + + return true; +} + +static bool +wmem_tree_destroy_cb(wmem_allocator_t *allocator _U_, wmem_cb_event_t event _U_, + void *user_data) +{ + wmem_tree_t *tree = (wmem_tree_t *)user_data; + + wmem_unregister_callback(tree->data_allocator, tree->data_scope_cb_id); + + return false; +} + +wmem_tree_t * +wmem_tree_new_autoreset(wmem_allocator_t *metadata_scope, wmem_allocator_t *data_scope) +{ + wmem_tree_t *tree; + + tree = wmem_new0(metadata_scope, wmem_tree_t); + tree->metadata_allocator = metadata_scope; + tree->data_allocator = data_scope; + + tree->metadata_scope_cb_id = wmem_register_callback(metadata_scope, wmem_tree_destroy_cb, + tree); + tree->data_scope_cb_id = wmem_register_callback(data_scope, wmem_tree_reset_cb, + tree); + + return tree; +} + +static void +free_tree_node(wmem_allocator_t *allocator, wmem_tree_node_t* node, bool free_keys, bool free_values) +{ + if (node == NULL) { + return; + } + + if (node->left) { + free_tree_node(allocator, node->left, free_keys, free_values); + } + + if (node->is_subtree) { + wmem_tree_destroy((wmem_tree_t *)node->data, free_keys, free_values); + node->data = NULL; + } + + if (node->right) { + free_tree_node(allocator, node->right, free_keys, free_values); + } + + if (free_keys) { + wmem_free(allocator, (void*)node->key); + } + + if (free_values) { + wmem_free(allocator, node->data); + } + wmem_free(allocator, node); +} + +void +wmem_tree_destroy(wmem_tree_t *tree, bool free_keys, bool free_values) +{ + free_tree_node(tree->data_allocator, tree->root, free_keys, free_values); + if (tree->metadata_allocator) { + wmem_unregister_callback(tree->metadata_allocator, tree->metadata_scope_cb_id); + } + if (tree->data_allocator) { + wmem_unregister_callback(tree->data_allocator, tree->data_scope_cb_id); + } + wmem_free(tree->metadata_allocator, tree); +} + +bool +wmem_tree_is_empty(wmem_tree_t *tree) +{ + return tree->root == NULL; +} + +static bool +count_nodes(const void *key _U_, void *value _U_, void *userdata) +{ + unsigned* count = (unsigned*)userdata; + (*count)++; + return false; +} + +unsigned +wmem_tree_count(wmem_tree_t* tree) +{ + unsigned count = 0; + + /* Recursing through the tree counting each node is the simplest approach. + We don't keep track of the count within the tree because it can get + complicated with subtrees within the tree */ + wmem_tree_foreach(tree, count_nodes, &count); + + return count; +} + +static wmem_tree_node_t * +create_node(wmem_allocator_t *allocator, wmem_tree_node_t *parent, const void *key, + void *data, wmem_node_color_t color, bool is_subtree) +{ + wmem_tree_node_t *node; + + node = wmem_new(allocator, wmem_tree_node_t); + + node->left = NULL; + node->right = NULL; + node->parent = parent; + + node->key = key; + node->data = data; + + node->color = color; + node->is_subtree = is_subtree; + node->is_removed = false; + + return node; +} + +#define CREATE_DATA(TRANSFORM, DATA) ((TRANSFORM) ? (TRANSFORM)(DATA) : (DATA)) + + +/** + * return inserted node + */ +static wmem_tree_node_t * +lookup_or_insert32_node(wmem_tree_t *tree, uint32_t key, + void*(*func)(void*), void* data, bool is_subtree, bool replace) +{ + wmem_tree_node_t *node = tree->root; + wmem_tree_node_t *new_node = NULL; + + /* is this the first node ?*/ + if (!node) { + new_node = create_node(tree->data_allocator, NULL, GUINT_TO_POINTER(key), + CREATE_DATA(func, data), WMEM_NODE_COLOR_BLACK, is_subtree); + tree->root = new_node; + return new_node; + } + + /* it was not the new root so walk the tree until we find where to + * insert this new leaf. + */ + while (!new_node) { + /* this node already exists, so just return the data pointer*/ + if (key == GPOINTER_TO_UINT(node->key)) { + if (replace) { + node->data = CREATE_DATA(func, data); + } + return node; + } + else if (key < GPOINTER_TO_UINT(node->key)) { + if (node->left) { + node = node->left; + } + else { + /* new node to the left */ + new_node = create_node(tree->data_allocator, node, GUINT_TO_POINTER(key), + CREATE_DATA(func, data), WMEM_NODE_COLOR_RED, + is_subtree); + node->left = new_node; + } + } + else if (key > GPOINTER_TO_UINT(node->key)) { + if (node->right) { + node = node->right; + } + else { + /* new node to the right */ + new_node = create_node(tree->data_allocator, node, GUINT_TO_POINTER(key), + CREATE_DATA(func, data), WMEM_NODE_COLOR_RED, + is_subtree); + node->right = new_node; + } + } + } + + /* node will now point to the newly created node */ + rb_insert_case1(tree, new_node); + + return new_node; +} + + +static void * +lookup_or_insert32(wmem_tree_t *tree, uint32_t key, + void*(*func)(void*), void* data, bool is_subtree, bool replace) +{ + wmem_tree_node_t *node = lookup_or_insert32_node(tree, key, func, data, is_subtree, replace); + return node->data; +} + +static void * +wmem_tree_lookup(wmem_tree_t *tree, const void *key, compare_func cmp) +{ + wmem_tree_node_t *node; + + if (tree == NULL || key == NULL) { + return NULL; + } + + node = tree->root; + + while (node) { + int result = cmp(key, node->key); + if (result == 0) { + return node->data; + } + else if (result < 0) { + node = node->left; + } + else if (result > 0) { + node = node->right; + } + } + + return NULL; +} + +wmem_tree_node_t * +wmem_tree_insert(wmem_tree_t *tree, const void *key, void *data, compare_func cmp) +{ + wmem_tree_node_t *node = tree->root; + wmem_tree_node_t *new_node = NULL; + + /* is this the first node ?*/ + if (!node) { + tree->root = create_node(tree->data_allocator, node, key, + data, WMEM_NODE_COLOR_BLACK, false); + return tree->root; + } + + /* it was not the new root so walk the tree until we find where to + * insert this new leaf. + */ + while (!new_node) { + int result = cmp(key, node->key); + if (result == 0) { + node->data = data; + node->is_removed = data ? false : true; + return node; + } + else if (result < 0) { + if (node->left) { + node = node->left; + } + else { + new_node = create_node(tree->data_allocator, node, key, + data, WMEM_NODE_COLOR_RED, false); + node->left = new_node; + } + } + else if (result > 0) { + if (node->right) { + node = node->right; + } + else { + /* new node to the right */ + new_node = create_node(tree->data_allocator, node, key, + data, WMEM_NODE_COLOR_RED, false); + node->right = new_node; + } + } + } + + /* node will now point to the newly created node */ + rb_insert_case1(tree, new_node); + + return new_node; +} + +void +wmem_tree_insert32(wmem_tree_t *tree, uint32_t key, void *data) +{ + lookup_or_insert32(tree, key, NULL, data, false, true); +} + +bool wmem_tree_contains32(wmem_tree_t *tree, uint32_t key) +{ + if (!tree) { + return false; + } + + wmem_tree_node_t *node = tree->root; + + while (node) { + if (key == GPOINTER_TO_UINT(node->key)) { + return true; + } + else if (key < GPOINTER_TO_UINT(node->key)) { + node = node->left; + } + else if (key > GPOINTER_TO_UINT(node->key)) { + node = node->right; + } + } + + return false; +} + +void * +wmem_tree_lookup32(wmem_tree_t *tree, uint32_t key) +{ + if (!tree) { + return NULL; + } + + wmem_tree_node_t *node = tree->root; + + while (node) { + if (key == GPOINTER_TO_UINT(node->key)) { + return node->data; + } + else if (key < GPOINTER_TO_UINT(node->key)) { + node = node->left; + } + else if (key > GPOINTER_TO_UINT(node->key)) { + node = node->right; + } + } + + return NULL; +} + +void * +wmem_tree_lookup32_le(wmem_tree_t *tree, uint32_t key) +{ + if (!tree) { + return NULL; + } + + wmem_tree_node_t *node = tree->root; + + while (node) { + if (key == GPOINTER_TO_UINT(node->key)) { + return node->data; + } + else if (key < GPOINTER_TO_UINT(node->key)) { + if (node->left == NULL) { + break; + } + node = node->left; + } + else if (key > GPOINTER_TO_UINT(node->key)) { + if (node->right == NULL) { + break; + } + node = node->right; + } + } + + if (!node) { + return NULL; + } + + /* If we are still at the root of the tree this means that this node + * is either smaller than the search key and then we return this + * node or else there is no smaller key available and then + * we return NULL. + */ + if (node->parent == NULL) { + if (key > GPOINTER_TO_UINT(node->key)) { + return node->data; + } else { + return NULL; + } + } + + if (GPOINTER_TO_UINT(node->key) <= key) { + /* if our key is <= the search key, we have the right node */ + return node->data; + } + else if (node == node->parent->left) { + /* our key is bigger than the search key and we're a left child, + * we have to check if any of our ancestors are smaller. */ + while (node) { + if (key > GPOINTER_TO_UINT(node->key)) { + return node->data; + } + node=node->parent; + } + return NULL; + } + else { + /* our key is bigger than the search key and we're a right child, + * our parent is the one we want */ + return node->parent->data; + } +} + +void * +wmem_tree_remove32(wmem_tree_t *tree, uint32_t key) +{ + void *ret = wmem_tree_lookup32(tree, key); + if (ret) { + /* Not really a remove, but set data to NULL to mark node with is_removed */ + wmem_tree_insert32(tree, key, NULL); + } + return ret; +} + +void +wmem_tree_insert_string(wmem_tree_t* tree, const char* k, void* v, uint32_t flags) +{ + char *key; + compare_func cmp; + + key = wmem_strdup(tree->data_allocator, k); + + if (flags & WMEM_TREE_STRING_NOCASE) { + cmp = (compare_func)g_ascii_strcasecmp; + } else { + cmp = (compare_func)strcmp; + } + + wmem_tree_insert(tree, key, v, cmp); +} + +void * +wmem_tree_lookup_string(wmem_tree_t* tree, const char* k, uint32_t flags) +{ + compare_func cmp; + + if (flags & WMEM_TREE_STRING_NOCASE) { + cmp = (compare_func)g_ascii_strcasecmp; + } else { + cmp = (compare_func)strcmp; + } + + return wmem_tree_lookup(tree, k, cmp); +} + +void * +wmem_tree_remove_string(wmem_tree_t* tree, const char* k, uint32_t flags) +{ + void *ret = wmem_tree_lookup_string(tree, k, flags); + if (ret) { + /* Not really a remove, but set data to NULL to mark node with is_removed */ + wmem_tree_insert_string(tree, k, NULL, flags); + } + return ret; +} + +static void * +create_sub_tree(void* d) +{ + return wmem_tree_new(((wmem_tree_t *)d)->data_allocator); +} + +void +wmem_tree_insert32_array(wmem_tree_t *tree, wmem_tree_key_t *key, void *data) +{ + wmem_tree_t *insert_tree = NULL; + wmem_tree_key_t *cur_key; + uint32_t i, insert_key32 = 0; + + for (cur_key = key; cur_key->length > 0; cur_key++) { + for (i = 0; i < cur_key->length; i++) { + /* Insert using the previous key32 */ + if (!insert_tree) { + insert_tree = tree; + } else { + insert_tree = (wmem_tree_t *)lookup_or_insert32(insert_tree, + insert_key32, create_sub_tree, tree, true, false); + } + insert_key32 = cur_key->key[i]; + } + } + + ws_assert(insert_tree); + + wmem_tree_insert32(insert_tree, insert_key32, data); +} + +static void * +wmem_tree_lookup32_array_helper(wmem_tree_t *tree, wmem_tree_key_t *key, + void*(*helper)(wmem_tree_t*, uint32_t)) +{ + wmem_tree_t *lookup_tree = NULL; + wmem_tree_key_t *cur_key; + uint32_t i, lookup_key32 = 0; + + if (!tree || !key) { + return NULL; + } + + for (cur_key = key; cur_key->length > 0; cur_key++) { + for (i = 0; i < cur_key->length; i++) { + /* Lookup using the previous key32 */ + if (!lookup_tree) { + lookup_tree = tree; + } + else { + lookup_tree = + (wmem_tree_t *)(*helper)(lookup_tree, lookup_key32); + if (!lookup_tree) { + return NULL; + } + } + lookup_key32 = cur_key->key[i]; + } + } + + /* Assert if we didn't get any valid keys */ + ws_assert(lookup_tree); + + return (*helper)(lookup_tree, lookup_key32); +} + +void * +wmem_tree_lookup32_array(wmem_tree_t *tree, wmem_tree_key_t *key) +{ + return wmem_tree_lookup32_array_helper(tree, key, wmem_tree_lookup32); +} + +void * +wmem_tree_lookup32_array_le(wmem_tree_t *tree, wmem_tree_key_t *key) +{ + return wmem_tree_lookup32_array_helper(tree, key, wmem_tree_lookup32_le); +} + +static bool +wmem_tree_foreach_nodes(wmem_tree_node_t* node, wmem_foreach_func callback, + void *user_data) +{ + bool stop_traverse = false; + + if (!node) { + return false; + } + + if (node->left) { + if (wmem_tree_foreach_nodes(node->left, callback, user_data)) { + return true; + } + } + + if (node->is_subtree) { + stop_traverse = wmem_tree_foreach((wmem_tree_t *)node->data, + callback, user_data); + } else if (!node->is_removed) { + /* No callback for "removed" nodes */ + stop_traverse = callback(node->key, node->data, user_data); + } + + if (stop_traverse) { + return true; + } + + if(node->right) { + if (wmem_tree_foreach_nodes(node->right, callback, user_data)) { + return true; + } + } + + return false; +} + +bool +wmem_tree_foreach(wmem_tree_t* tree, wmem_foreach_func callback, + void *user_data) +{ + if(!tree->root) + return false; + + return wmem_tree_foreach_nodes(tree->root, callback, user_data); +} + +static void wmem_print_subtree(wmem_tree_t *tree, uint32_t level, wmem_printer_func key_printer, wmem_printer_func data_printer); + +static void +wmem_print_indent(uint32_t level) { + uint32_t i; + for (i=0; iparent, + (void *)node->left, (void *)node->right, + node->color?"Black":"Red", node->key, + node->is_subtree?"tree":"data", node->data); + if (key_printer) { + wmem_print_indent(level); + key_printer(node->key); + printf("\n"); + } + if (data_printer && !node->is_subtree) { + wmem_print_indent(level); + data_printer(node->data); + printf("\n"); + } + + if (node->left) + wmem_tree_print_nodes("L-", node->left, level+1, key_printer, data_printer); + if (node->right) + wmem_tree_print_nodes("R-", node->right, level+1, key_printer, data_printer); + + if (node->is_subtree) + wmem_print_subtree((wmem_tree_t *)node->data, level+1, key_printer, data_printer); +} + + +static void +wmem_print_subtree(wmem_tree_t *tree, uint32_t level, wmem_printer_func key_printer, wmem_printer_func data_printer) +{ + if (!tree) + return; + + wmem_print_indent(level); + + printf("WMEM tree:%p root:%p\n", (void *)tree, (void *)tree->root); + if (tree->root) { + wmem_tree_print_nodes("Root-", tree->root, level, key_printer, data_printer); + } +} + +void +wmem_print_tree(wmem_tree_t *tree, wmem_printer_func key_printer, wmem_printer_func data_printer) +{ + wmem_print_subtree(tree, 0, key_printer, data_printer); +} +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_tree.h b/wsutil/wmem/wmem_tree.h new file mode 100644 index 00000000..f639ff9a --- /dev/null +++ b/wsutil/wmem/wmem_tree.h @@ -0,0 +1,263 @@ +/** @file + * Definitions for the Wireshark Memory Manager Red-Black Tree + * Based on the red-black tree implementation in epan/emem.* + * Copyright 2013, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#ifndef __WMEM_TREE_H__ +#define __WMEM_TREE_H__ + +#include "wmem_core.h" + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +/** @addtogroup wmem + * @{ + * @defgroup wmem-tree Red/Black Tree + * + * Binary trees are a well-known and popular device in computer science to + * handle storage of objects based on a search key or identity. The + * particular binary tree style implemented here is the red/black tree, which + * has the nice property of being self-balancing. This guarantees O(log(n)) + * time for lookups, compared to linked lists that are O(n). This means + * red/black trees scale very well when many objects are being stored. + * + * @{ + */ + +struct _wmem_tree_t; +typedef struct _wmem_tree_t wmem_tree_t; + +/** Creates a tree with the given allocator scope. When the scope is emptied, + * the tree is fully destroyed. */ +WS_DLL_PUBLIC +wmem_tree_t * +wmem_tree_new(wmem_allocator_t *allocator) +G_GNUC_MALLOC; + +/** Creates a tree with two allocator scopes. The base structure lives in the + * metadata scope, and the tree data lives in the data scope. Every time free_all + * occurs in the data scope the tree is transparently emptied without affecting + * the location of the base / metadata structure. + * + * WARNING: None of the tree (even the part in the metadata scope) can be used + * after the data scope has been *destroyed*. + * + * The primary use for this function is to create trees that reset for each new + * capture file that is loaded. This can be done by specifying wmem_epan_scope() + * as the metadata scope and wmem_file_scope() as the data scope. + */ +WS_DLL_PUBLIC +wmem_tree_t * +wmem_tree_new_autoreset(wmem_allocator_t *metadata_scope, wmem_allocator_t *data_scope) +G_GNUC_MALLOC; + +/** Cleanup memory used by tree. Intended for NULL scope allocated trees */ +WS_DLL_PUBLIC +void +wmem_tree_destroy(wmem_tree_t *tree, bool free_keys, bool free_values); + +/** Returns true if the tree is empty (has no nodes). */ +WS_DLL_PUBLIC +bool +wmem_tree_is_empty(wmem_tree_t *tree); + +/** Returns number of nodes in tree */ +WS_DLL_PUBLIC +unsigned +wmem_tree_count(wmem_tree_t* tree); + +/** Insert a node indexed by a uint32_t key value. + * + * Data is a pointer to the structure you want to be able to retrieve by + * searching for the same key later. + * + * NOTE: If you insert a node to a key that already exists in the tree this + * function will simply overwrite the old value. If the structures you are + * storing are allocated in a wmem pool this is not a problem as they will still + * be freed with the pool. If you are managing them manually however, you must + * either ensure the key is unique, or do a lookup before each insert. + */ +WS_DLL_PUBLIC +void +wmem_tree_insert32(wmem_tree_t *tree, uint32_t key, void *data); + +/** Look up a node in the tree indexed by a uint32_t integer value. Return true + * if present. + */ +WS_DLL_PUBLIC +bool +wmem_tree_contains32(wmem_tree_t *tree, uint32_t key); + +/** Look up a node in the tree indexed by a uint32_t integer value. If no node is + * found the function will return NULL. + */ +WS_DLL_PUBLIC +void * +wmem_tree_lookup32(wmem_tree_t *tree, uint32_t key); + +/** Look up a node in the tree indexed by a uint32_t integer value. + * Returns the node that has the largest key that is less than or equal + * to the search key, or NULL if no such key exists. + */ +WS_DLL_PUBLIC +void * +wmem_tree_lookup32_le(wmem_tree_t *tree, uint32_t key); + +/** Remove a node in the tree indexed by a uint32_t integer value. This is not + * really a remove, but the value is set to NULL so that wmem_tree_lookup32 + * not will find it. + */ +WS_DLL_PUBLIC +void * +wmem_tree_remove32(wmem_tree_t *tree, uint32_t key); + +/** case insensitive strings as keys */ +#define WMEM_TREE_STRING_NOCASE 0x00000001 +/** Insert a new value under a string key. Like wmem_tree_insert32 but where the + * key is a null-terminated string instead of a uint32_t. You may pass + * WMEM_TREE_STRING_NOCASE to the flags argument in order to make it store the + * key in a case-insensitive way. (Note that "case-insensitive" refers + * only to the ASCII letters A-Z and a-z; it is locale-independent. + * Do not expect it to honor the rules of your language; for example, "I" + * will always be mapped to "i". */ +WS_DLL_PUBLIC +void +wmem_tree_insert_string(wmem_tree_t *tree, const char* key, void *data, + uint32_t flags); + +/** Lookup the value under a string key, like wmem_tree_lookup32 but where the + * keye is a null-terminated string instead of a uint32_t. See + * wmem_tree_insert_string for an explanation of flags. */ +WS_DLL_PUBLIC +void * +wmem_tree_lookup_string(wmem_tree_t* tree, const char* key, uint32_t flags); + +/** Remove the value under a string key. This is not really a remove, but the + * value is set to NULL so that wmem_tree_lookup_string not will find it. + * See wmem_tree_insert_string for an explanation of flags. */ +WS_DLL_PUBLIC +void * +wmem_tree_remove_string(wmem_tree_t* tree, const char* key, uint32_t flags); + +typedef struct _wmem_tree_key_t { + uint32_t length; /**< length in uint32_t words */ + uint32_t *key; +} wmem_tree_key_t; + +/** Insert a node indexed by a sequence of uint32_t key values. + * + * Takes as key an array of uint32_t vectors of type wmem_tree_key_t. It will + * iterate through each key to search further down the tree until it reaches an + * element where length==0, indicating the end of the array. You MUST terminate + * the key array by {0, NULL} or this will crash. + * + * NOTE: length indicates the number of uint32_t values in the vector, not the + * number of bytes. + * + * NOTE: all the "key" members of the "key" argument MUST be aligned on + * 32-bit boundaries; otherwise, this code will crash on platforms such + * as SPARC that require aligned pointers. + * + * If you use ...32_array() calls you MUST make sure that every single node + * you add to a specific tree always has a key of exactly the same number of + * keylen words or it will crash. Or at least that every single item that sits + * behind the same top level node always has exactly the same number of words. + * + * One way to guarantee this is the way that NFS does this for the + * nfs_name_snoop_known tree which holds filehandles for both v2 and v3. + * v2 filehandles are always 32 bytes (8 words) while v3 filehandles can have + * any length (though 32 bytes are most common). + * The NFS dissector handles this by providing a uint32_t containing the length + * as the very first item in this vector : + * + * wmem_tree_key_t fhkey[3]; + * + * fhlen=nns->fh_length; + * fhkey[0].length=1; + * fhkey[0].key=&fhlen; + * fhkey[1].length=fhlen/4; + * fhkey[1].key=nns->fh; + * fhkey[2].length=0; + */ +WS_DLL_PUBLIC +void +wmem_tree_insert32_array(wmem_tree_t *tree, wmem_tree_key_t *key, void *data); + +/** Look up a node in the tree indexed by a sequence of uint32_t integer values. + * See wmem_tree_insert32_array for details on the key. + */ +WS_DLL_PUBLIC +void * +wmem_tree_lookup32_array(wmem_tree_t *tree, wmem_tree_key_t *key); + +/** Look up a node in the tree indexed by a multi-part tree value. + * The function will return the node that has the largest key that is + * equal to or smaller than the search key, or NULL if no such key was + * found. + * + * NOTE: The key returned will be "less" in key order. The usefulness + * of the returned node must be verified prior to use. + * + * See wmem_tree_insert32_array for details on the key. + */ +WS_DLL_PUBLIC +void * +wmem_tree_lookup32_array_le(wmem_tree_t *tree, wmem_tree_key_t *key); + +/** Function type for processing one node of a tree during a traversal. Value is + * the value of the node, userdata is whatever was passed to the traversal + * function. If the function returns true the traversal will end prematurely. + */ +typedef bool (*wmem_foreach_func)(const void *key, void *value, void *userdata); + + +/** Function type to print key/data of nodes in wmem_print_tree_verbose */ +typedef void (*wmem_printer_func)(const void *data); + + +/** Inorder traversal (left/parent/right) of the tree and call + * callback(value, userdata) for each value found. + * + * Returns true if the traversal was ended prematurely by the callback. + */ +WS_DLL_PUBLIC +bool +wmem_tree_foreach(wmem_tree_t* tree, wmem_foreach_func callback, + void *user_data); + + +/* Accepts callbacks to print the key and/or data (both printers can be null) */ +WS_DLL_PUBLIC +void +wmem_print_tree(wmem_tree_t *tree, wmem_printer_func key_printer, wmem_printer_func data_printer); + +/** @} + * @} */ + +#ifdef __cplusplus +} +#endif /* __cplusplus */ + +#endif /* __WMEM_TREE_H__ */ + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_user_cb.c b/wsutil/wmem/wmem_user_cb.c new file mode 100644 index 00000000..232b1692 --- /dev/null +++ b/wsutil/wmem/wmem_user_cb.c @@ -0,0 +1,104 @@ +/* wmem_user_cb.c + * Wireshark Memory Manager User Callbacks + * Copyright 2012, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#include "wmem_core.h" +#include "wmem_allocator.h" + +#include "wmem_user_cb.h" +#include "wmem_user_cb_int.h" + +typedef struct _wmem_user_cb_container_t { + wmem_user_cb_t cb; + void *user_data; + struct _wmem_user_cb_container_t *next; + unsigned id; +} wmem_user_cb_container_t; + +void +wmem_call_callbacks(wmem_allocator_t *allocator, wmem_cb_event_t event) +{ + wmem_user_cb_container_t **prev, *cur; + bool again; + + prev = &(allocator->callbacks); + cur = allocator->callbacks; + + while (cur) { + + /* call it */ + again = cur->cb(allocator, event, cur->user_data); + + /* if the callback requested deregistration, or this is being triggered + * by the final destruction of the allocator, remove the callback */ + if (! again || event == WMEM_CB_DESTROY_EVENT) { + *prev = cur->next; + wmem_free(NULL, cur); + cur = *prev; + } + else { + prev = &(cur->next); + cur = cur->next; + } + } +} + +unsigned +wmem_register_callback(wmem_allocator_t *allocator, + wmem_user_cb_t callback, void *user_data) +{ + wmem_user_cb_container_t *container; + static unsigned next_id = 1; + + container = wmem_new(NULL, wmem_user_cb_container_t); + + container->cb = callback; + container->user_data = user_data; + container->next = allocator->callbacks; + container->id = next_id++; + + allocator->callbacks = container; + + return container->id; +} + +void +wmem_unregister_callback(wmem_allocator_t *allocator, unsigned id) +{ + wmem_user_cb_container_t **prev, *cur; + + prev = &(allocator->callbacks); + cur = allocator->callbacks; + + while (cur) { + + if (cur->id == id) { + *prev = cur->next; + wmem_free(NULL, cur); + return; + } + + prev = &(cur->next); + cur = cur->next; + } +} + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_user_cb.h b/wsutil/wmem/wmem_user_cb.h new file mode 100644 index 00000000..7d2a37e3 --- /dev/null +++ b/wsutil/wmem/wmem_user_cb.h @@ -0,0 +1,92 @@ +/** @file + * Definitions for the Wireshark Memory Manager User Callbacks + * Copyright 2012, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#ifndef __WMEM_USER_CB_H__ +#define __WMEM_USER_CB_H__ + +#include + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +/** @addtogroup wmem + * @{ + * @defgroup wmem-user-cb User Callbacks + * + * User callbacks. + * + * @{ + */ + +/** The events that can trigger a callback. */ +typedef enum _wmem_cb_event_t { + WMEM_CB_FREE_EVENT, /**< wmem_free_all() */ + WMEM_CB_DESTROY_EVENT /**< wmem_destroy_allocator() */ +} wmem_cb_event_t; + +/** Function signature for registered user callbacks. + * + * allocator The allocator that triggered this callback. + * event The event type that triggered this callback. + * user_data Whatever user_data was originally passed to the call to + * wmem_register_callback(). + * @return false to unregister the callback, true otherwise. + */ +typedef bool (*wmem_user_cb_t) (wmem_allocator_t*, wmem_cb_event_t, void*); + +/** Register a callback function with the given allocator pool. + * + * @param allocator The allocator with which to register the callback. + * @param callback The function to be called as the callback. + * @param user_data An arbitrary data pointer that is passed to the callback as + * a way to specify extra parameters or store extra data. Note + * that this pointer is not freed when a callback is finished, + * you have to do that yourself in the callback, or just + * allocate it in the appropriate wmem pool. + * @return ID of this callback that can be passed back to + * wmem_unregister_callback(). + */ +WS_DLL_PUBLIC +unsigned +wmem_register_callback(wmem_allocator_t *allocator, wmem_user_cb_t callback, + void *user_data); + +/** Unregister the callback function with the given ID. + * + * @param allocator The allocator from which to unregister the callback. + * @param id The callback id as returned from wmem_register_callback(). + */ +WS_DLL_PUBLIC +void +wmem_unregister_callback(wmem_allocator_t *allocator, unsigned id); + +/** @} + * @} */ + +#ifdef __cplusplus +} +#endif /* __cplusplus */ + +#endif /* __WMEM_USER_CB_H__ */ + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ diff --git a/wsutil/wmem/wmem_user_cb_int.h b/wsutil/wmem/wmem_user_cb_int.h new file mode 100644 index 00000000..9f3ed58a --- /dev/null +++ b/wsutil/wmem/wmem_user_cb_int.h @@ -0,0 +1,45 @@ +/** @file + * + * Definitions for the Wireshark Memory Manager User Callback Internals + * Copyright 2012, Evan Huus + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#ifndef __WMEM_USER_CB_INT_H__ +#define __WMEM_USER_CB_INT_H__ + +#include + +#include "wmem_user_cb.h" + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +WS_DLL_LOCAL +void +wmem_call_callbacks(wmem_allocator_t *allocator, wmem_cb_event_t event); + +#ifdef __cplusplus +} +#endif /* __cplusplus */ + +#endif /* __WMEM_USER_CB_INT_H__ */ + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ -- cgit v1.2.3