From 7f9c1f5f92c131354fc8b2b88d473706786064c0 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Jo=C3=A3o=20Valverde?= Date: Mon, 12 Jul 2021 21:22:05 +0100 Subject: Move wmem to wsutil This allows wmem to be used from other libraries, namely wsutil. It is often the case that a funtion exists in wsutil and cannot be used with a wmem scope, requiring some code duplication or extra memory allocations, or vice-versa, code in epan cannot be moved to wsutil because it has a wmem dependency. To this end wmem is moved to wsutil. Scope management remains part of epan because those scope semantics are specific to dissection. --- wsutil/CMakeLists.txt | 3 + wsutil/wmem/CMakeLists.txt | 115 +++ wsutil/wmem/wmem-int.h | 36 + wsutil/wmem/wmem.h | 41 + wsutil/wmem/wmem_allocator.h | 63 ++ wsutil/wmem/wmem_allocator_block.c | 1125 +++++++++++++++++++++++ wsutil/wmem/wmem_allocator_block.h | 45 + wsutil/wmem/wmem_allocator_block_fast.c | 258 ++++++ wsutil/wmem/wmem_allocator_block_fast.h | 40 + wsutil/wmem/wmem_allocator_simple.c | 152 ++++ wsutil/wmem/wmem_allocator_simple.h | 41 + wsutil/wmem/wmem_allocator_strict.c | 230 +++++ wsutil/wmem/wmem_allocator_strict.h | 44 + wsutil/wmem/wmem_array.c | 179 ++++ wsutil/wmem/wmem_array.h | 111 +++ wsutil/wmem/wmem_core.c | 240 +++++ wsutil/wmem/wmem_core.h | 244 +++++ wsutil/wmem/wmem_interval_tree.c | 188 ++++ wsutil/wmem/wmem_interval_tree.h | 101 +++ wsutil/wmem/wmem_list.c | 274 ++++++ wsutil/wmem/wmem_list.h | 128 +++ wsutil/wmem/wmem_map.c | 487 ++++++++++ wsutil/wmem/wmem_map.h | 231 +++++ wsutil/wmem/wmem_map_int.h | 40 + wsutil/wmem/wmem_miscutl.c | 49 + wsutil/wmem/wmem_miscutl.h | 70 ++ wsutil/wmem/wmem_queue.h | 69 ++ wsutil/wmem/wmem_stack.c | 57 ++ wsutil/wmem/wmem_stack.h | 73 ++ wsutil/wmem/wmem_strbuf.c | 308 +++++++ wsutil/wmem/wmem_strbuf.h | 120 +++ wsutil/wmem/wmem_strutl.c | 337 +++++++ wsutil/wmem/wmem_strutl.h | 124 +++ wsutil/wmem/wmem_test.c | 1485 +++++++++++++++++++++++++++++++ wsutil/wmem/wmem_tree-int.h | 84 ++ wsutil/wmem/wmem_tree.c | 838 +++++++++++++++++ wsutil/wmem/wmem_tree.h | 255 ++++++ wsutil/wmem/wmem_user_cb.c | 104 +++ wsutil/wmem/wmem_user_cb.h | 92 ++ wsutil/wmem/wmem_user_cb_int.h | 44 + 40 files changed, 8525 insertions(+) create mode 100644 wsutil/wmem/CMakeLists.txt 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_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') diff --git a/wsutil/CMakeLists.txt b/wsutil/CMakeLists.txt index 9e9b62c89c..e636bb3196 100644 --- a/wsutil/CMakeLists.txt +++ b/wsutil/CMakeLists.txt @@ -11,6 +11,8 @@ add_definitions(-DPLUGIN_DIR=\"${CMAKE_INSTALL_PREFIX}/${PLUGIN_INSTALL_LIBDIR}\ add_definitions(-DEXTCAP_DIR=\"${CMAKE_INSTALL_PREFIX}/${EXTCAP_INSTALL_LIBDIR}\") add_definitions(-DDATA_DIR=\"${CMAKE_INSTALL_PREFIX}/${CMAKE_INSTALL_DATADIR}\") +add_subdirectory(wmem) + set(WSUTIL_PUBLIC_HEADERS 802_11-utils.h adler32.h @@ -248,6 +250,7 @@ endif() add_library(wsutil ${WSUTIL_FILES} + $ ${CMAKE_BINARY_DIR}/image/libwsutil.rc ) diff --git a/wsutil/wmem/CMakeLists.txt b/wsutil/wmem/CMakeLists.txt new file mode 100644 index 0000000000..d3d4e88db5 --- /dev/null +++ b/wsutil/wmem/CMakeLists.txt @@ -0,0 +1,115 @@ +# CMakeLists.txt +# +# Wireshark - Network traffic analyzer +# By Gerald Combs +# Copyright 1998 Gerald Combs +# +# SPDX-License-Identifier: GPL-2.0-or-later +# + +set(WMEM_PUBLIC_HEADERS + wmem.h + wmem_array.h + wmem_core.h + wmem_list.h + wmem_map.h + wmem_miscutl.h + wmem_queue.h + wmem_stack.h + wmem_strbuf.h + wmem_strutl.h + wmem_tree.h + wmem_interval_tree.h + wmem_user_cb.h +) + +set(WMEM_HEADER_FILES + ${WMEM_PUBLIC_HEADERS} + wmem_allocator.h + wmem_allocator_block.h + wmem_allocator_block_fast.h + wmem_allocator_simple.h + wmem_allocator_strict.h + wmem_interval_tree.h + wmem_map_int.h + wmem_tree-int.h + wmem_user_cb_int.h +) + +set(WMEM_FILES + wmem_array.c + wmem_core.c + wmem_allocator_block.c + wmem_allocator_block_fast.c + wmem_allocator_simple.c + wmem_allocator_strict.c + wmem_interval_tree.c + wmem_list.c + wmem_map.c + wmem_miscutl.c + wmem_stack.c + wmem_strbuf.c + wmem_strutl.c + wmem_tree.c + wmem_user_cb.c +) +source_group(wmem FILES ${WMEM_FILES}) + +set_source_files_properties( + ${WMEM_FILES} + PROPERTIES + COMPILE_FLAGS "${WERROR_COMMON_FLAGS}" +) + +add_library(wmem OBJECT + #Included so that Visual Studio can properly put header files in solution + ${WMEM_HEADER_FILES} + + ${WMEM_FILES} +) + +target_include_directories(wmem + PRIVATE + ${CMAKE_CURRENT_BINARY_DIR} + ${CMAKE_CURRENT_SOURCE_DIR} +) + +set_target_properties(wmem PROPERTIES + FOLDER "Libs/wsutil/wmem" + COMPILE_DEFINITIONS "WS_BUILD_DLL" +) + +add_executable(wmem_test EXCLUDE_FROM_ALL wmem_test.c $) + +target_link_libraries(wmem_test wsutil) + +set_target_properties(wmem_test PROPERTIES + FOLDER "Tests" + EXCLUDE_FROM_DEFAULT_BUILD True + COMPILE_DEFINITIONS "WS_BUILD_DLL" +) + +install(FILES ${WMEM_PUBLIC_HEADERS} + DESTINATION "${PROJECT_INSTALL_INCLUDEDIR}/wsutil/wmem" +) + +CHECKAPI( + NAME + wmem + SWITCHES + SOURCES + ${WMEM_FILES} +) + +# +# Editor modelines - https://www.wireshark.org/tools/modelines.html +# +# Local variables: +# c-basic-offset: 8 +# tab-width: 8 +# indent-tabs-mode: t +# End: +# +# vi: set shiftwidth=8 tabstop=8 noexpandtab: +# :indentSize=8:tabSize=8:noTabs=false: +# diff --git a/wsutil/wmem/wmem-int.h b/wsutil/wmem/wmem-int.h new file mode 100644 index 0000000000..5f3ba1dde2 --- /dev/null +++ b/wsutil/wmem/wmem-int.h @@ -0,0 +1,36 @@ +/* wmem-int.h + * 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 + +#ifdef WS_DISABLE_ASSERT +#define ASSERT(...) (void)0 +#else +#define ASSERT(...) g_assert(__VA_ARGS__) +#endif /* WS_DISABLE_ASSERT */ + +#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 0000000000..65f06fdc04 --- /dev/null +++ b/wsutil/wmem/wmem.h @@ -0,0 +1,41 @@ +/* wmem.h + * 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_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 0000000000..4bc3487b85 --- /dev/null +++ b/wsutil/wmem/wmem_allocator.h @@ -0,0 +1,63 @@ +/* wmem_allocator.h + * 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; + gboolean 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 0000000000..070d472307 --- /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 (gsize)) +#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 { + guint32 prev; + + /* flags */ + guint32 last:1; + guint32 used:1; + guint32 jumbo:1; + + guint32 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*)(((guint8*)(CHUNK)) - (CHUNK)->prev)) \ + : NULL) + +#define WMEM_CHUNK_NEXT(CHUNK) ((CHUNK)->last \ + ? NULL \ + : ((wmem_block_chunk_t*)(((guint8*)(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*)((guint8*)(CHUNK) + WMEM_CHUNK_HEADER_SIZE)) +#define WMEM_DATA_TO_CHUNK(DATA) ((wmem_block_chunk_t*)((guint8*)(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*)((guint8*)(BLOCK) + WMEM_BLOCK_HEADER_SIZE)) +#define WMEM_CHUNK_TO_BLOCK(CHUNK) ((wmem_block_hdr_t*)((guint8*)(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; + guint32 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; + gboolean 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 = (guint32) 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 = (guint32) 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; + gboolean 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 = (guint32) 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 = (guint32) 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 0000000000..a56757b42b --- /dev/null +++ b/wsutil/wmem/wmem_allocator_block.h @@ -0,0 +1,45 @@ +/* wmem_allocator_block.h + * 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 0000000000..bdb8c2f75d --- /dev/null +++ b/wsutil/wmem/wmem_allocator_block_fast.c @@ -0,0 +1,258 @@ +/* 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 (gsize)) +#define WMEM_ALIGN_SIZE(SIZE) ((~(WMEM_ALIGN_AMOUNT-1)) & \ + ((SIZE) + (WMEM_ALIGN_AMOUNT-1))) + +#define WMEM_CHUNK_TO_DATA(CHUNK) ((void*)((guint8*)(CHUNK) + WMEM_CHUNK_HEADER_SIZE)) +#define WMEM_DATA_TO_CHUNK(DATA) ((wmem_block_fast_chunk_t*)((guint8*)(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; + + gint32 pos; +} wmem_block_fast_hdr_t; +#define WMEM_BLOCK_HEADER_SIZE WMEM_ALIGN_SIZE(sizeof(wmem_block_fast_hdr_t)) + +typedef struct { + guint32 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; + gint32 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; + block->prev = NULL; + allocator->jumbo_list = block; + + chunk = ((wmem_block_fast_chunk_t*)((guint8*)(block) + WMEM_JUMBO_HEADER_SIZE)); + chunk->len = JUMBO_MAGIC; + + return WMEM_CHUNK_TO_DATA(chunk); + } + + real_size = (gint32)(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 *) ((guint8 *) allocator->block_list + allocator->block_list->pos); + /* safe to cast, size smaller than WMEM_BLOCK_MAX_ALLOC_SIZE */ + chunk->len = (guint32) 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*)((guint8*)(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*)((guint8*)(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 0000000000..d17d40ca80 --- /dev/null +++ b/wsutil/wmem/wmem_allocator_block_fast.h @@ -0,0 +1,40 @@ +/* wmem_allocator_block_fast.h + * 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 0000000000..0c7d9b0be4 --- /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 0000000000..4c045bdd65 --- /dev/null +++ b/wsutil/wmem/wmem_allocator_simple.h @@ -0,0 +1,41 @@ +/* wmem_allocator_simple.h + * 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 0000000000..8a84f58b8e --- /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 */ + gsize data_len; +} wmem_strict_allocator_block_t; + +#define WMEM_DATA_TO_BLOCK(DATA) ((wmem_strict_allocator_block_t*)((guint8*)(DATA) - WMEM_CANARY_SIZE - sizeof(wmem_strict_allocator_block_t))) +#define WMEM_BLOCK_TO_DATA(BLOCK) ((void*)((guint8*)(BLOCK) + WMEM_CANARY_SIZE + sizeof(wmem_strict_allocator_block_t))) +#define WMEM_BLOCK_TO_PRE_CANARY(BLOCK) ((guint8*)(BLOCK) + sizeof(wmem_strict_allocator_block_t)) +#define WMEM_BLOCK_TO_POST_CANARY(BLOCK) ((guint8*)(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) +{ + guint i; + guint8 *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 0000000000..5352090abd --- /dev/null +++ b/wsutil/wmem/wmem_allocator_strict.h @@ -0,0 +1,44 @@ +/* wmem_allocator_strict.h + * 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 0000000000..49ab45fdfa --- /dev/null +++ b/wsutil/wmem/wmem_array.c @@ -0,0 +1,179 @@ +/* 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; + + guint8 *buf; + + gsize elem_size; + + guint elem_count; + guint alloc_count; + + gboolean null_terminated; +}; + +wmem_array_t * +wmem_array_sized_new(wmem_allocator_t *allocator, gsize elem_size, + guint 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 = (guint8 *)wmem_alloc(array->allocator, + array->elem_size * array->alloc_count); + + return array; +} + +wmem_array_t * +wmem_array_new(wmem_allocator_t *allocator, const gsize 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 guint to_add) +{ + guint 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 = (guint8 *)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, guint 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, guint 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, guint 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; +} + +guint +wmem_array_get_count(wmem_array_t *array) +{ + return array->elem_count; +} + +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 0000000000..8f57fa4c2f --- /dev/null +++ b/wsutil/wmem/wmem_array.h @@ -0,0 +1,111 @@ +/* wmem_array.h + * 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, gsize elem_size, + guint alloc_count) +G_GNUC_MALLOC; + +WS_DLL_PUBLIC +wmem_array_t * +wmem_array_new(wmem_allocator_t *allocator, const gsize elem_size) +G_GNUC_MALLOC; + +WS_DLL_PUBLIC +void +wmem_array_grow(wmem_array_t *array, const guint 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, guint 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, guint array_index); + +WS_DLL_PUBLIC +int +wmem_array_try_index(wmem_array_t *array, guint 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 +guint +wmem_array_get_count(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 0000000000..a49730088d --- /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 gboolean 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); + } + + 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; + } + + 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; + } + + ASSERT(allocator->in_scope); + + return allocator->wrealloc(allocator->private_data, ptr, size); +} + +static void +wmem_free_all_real(wmem_allocator_t *allocator, gboolean 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; +} + +gboolean +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 0000000000..70330375a6 --- /dev/null +++ b/wsutil/wmem/wmem_core.h @@ -0,0 +1,244 @@ +/* wmem_core.h + * 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 "ws_attributes.h" + +#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))) + +#define wmem_safe_mult(A, B) \ + ((((A) <= 0) || ((B) <= 0) || ((gsize)(A) > (G_MAXSSIZE / (gsize)(B)))) ? 0 : ((A) * (B))) + +/** 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(sizeof(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(sizeof(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 +gboolean +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 0000000000..308fc5a4c3 --- /dev/null +++ b/wsutil/wmem/wmem_interval_tree.c @@ -0,0 +1,188 @@ +/* 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 "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=%" G_GUINT64_FORMAT " high=%" G_GUINT64_FORMAT " max_edge=%" G_GUINT64_FORMAT "\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; + guint64 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); + } +} + +gboolean +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; +} + +gboolean +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 guint64 low, const guint64 high, void *data) +{ + wmem_tree_node_t *node; + wmem_range_t *range = (wmem_range_t *)wmem_new(tree->data_allocator, wmem_range_t); + + 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, guint64 low, guint64 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 0000000000..5fb3172e5a --- /dev/null +++ b/wsutil/wmem/wmem_interval_tree.h @@ -0,0 +1,101 @@ +/* wmem_interval_tree.h + * 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 { + guint64 low; /* low is used as the key in the binary tree */ + guint64 high; /* Max value of the range */ + guint64 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 +gboolean +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 guint64 low, const guint64 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, guint64 low, guint64 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 0000000000..b54881b93c --- /dev/null +++ b/wsutil/wmem/wmem_list.c @@ -0,0 +1,274 @@ +/* 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 { + guint count; + wmem_list_frame_t *head, *tail; + wmem_allocator_t *allocator; +}; + +guint +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; + + 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, gpointer 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 0000000000..db17df0ba7 --- /dev/null +++ b/wsutil/wmem/wmem_list.h @@ -0,0 +1,128 @@ +/* wmem_list.h + * 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 +guint +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, gpointer 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 0000000000..0b6c2970a7 --- /dev/null +++ b/wsutil/wmem/wmem_map.c @@ -0,0 +1,487 @@ +/* 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 guint32 x; /* Used for universal integer hashing (see the HASH macro) */ + +/* Used for the wmem_strong_hash() function */ +static guint32 preseed; +static guint32 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 { + guint 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; + + guint metadata_scope_cb_id; + guint 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) \ + ((guint32)(((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 gboolean +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 gboolean +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; + guint 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; +} + +gboolean +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; +} + +gboolean +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; +} + +gboolean +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, gpointer 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((gpointer)cur->key, (gpointer)cur->value, user_data); + cur = cur->next; + } + } +} + +guint +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 + */ +guint32 +wmem_strong_hash(const guint8 *buf, const size_t len) +{ + const guint8 * const end = (const guint8 *)buf + len; + guint32 hash = preseed + (guint32)len; + + while (buf < end) { + hash += (hash << 10); + hash ^= (hash >> 6); + hash += *buf++; + } + + hash += (hash << 10); + hash ^= (hash >> 6); + hash += ((guint8*)&postseed)[0]; + + hash += (hash << 10); + hash ^= (hash >> 6); + hash += ((guint8*)&postseed)[1]; + + hash += (hash << 10); + hash ^= (hash >> 6); + hash += ((guint8*)&postseed)[2]; + + hash += (hash << 10); + hash ^= (hash >> 6); + hash += ((guint8*)&postseed)[3]; + + hash += (hash << 10); + hash ^= (hash >> 6); + + hash += (hash << 3); + hash ^= (hash >> 11); + return (hash + (hash << 15)); +} + +guint +wmem_str_hash(gconstpointer key) +{ + return wmem_strong_hash((const guint8 *)key, strlen((const char *)key)); +} + +guint +wmem_int64_hash(gconstpointer key) +{ + return wmem_strong_hash((const guint8 *)key, sizeof(guint64)); +} + +guint +wmem_double_hash(gconstpointer key) +{ + return wmem_strong_hash((const guint8 *)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 0000000000..4970e058ad --- /dev/null +++ b/wsutil/wmem/wmem_map.h @@ -0,0 +1,231 @@ +/* wmem_map.h + * 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" + +#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.gnome.org/glib/unstable/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 +gboolean +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 +gboolean +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 +gboolean +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, gpointer user_data); + +/** Return the number of elements of the map. + * + * @param map The map to use + * @return the number of elements +*/ +WS_DLL_PUBLIC +guint +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 +guint32 +wmem_strong_hash(const guint8 *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 +guint +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 +guint +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 +guint +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 0000000000..982c02435d --- /dev/null +++ b/wsutil/wmem/wmem_map_int.h @@ -0,0 +1,40 @@ +/* wmem_map_int.h + * 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 0000000000..eb75b90cb7 --- /dev/null +++ b/wsutil/wmem/wmem_miscutl.c @@ -0,0 +1,49 @@ +/* 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; +} + +gint +uint64_compare(gconstpointer a, gconstpointer b) +{ + return (guint64)(a) > (guint64)(b) ? 1 : ((guint64)(a) < (guint64)(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 0000000000..ccf65f06d8 --- /dev/null +++ b/wsutil/wmem/wmem_miscutl.h @@ -0,0 +1,70 @@ +/* wmem_miscutl.h + * 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 implementation to compare unsigned integer 64 bits long + */ +WS_DLL_PUBLIC +gint +uint64_compare(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_queue.h b/wsutil/wmem/wmem_queue.h new file mode 100644 index 0000000000..483278f3ee --- /dev/null +++ b/wsutil/wmem/wmem_queue.h @@ -0,0 +1,69 @@ +/* wmem_queue.h + * 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 0000000000..ae1f695b2a --- /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); + + 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 0000000000..9a30de511e --- /dev/null +++ b/wsutil/wmem/wmem_stack.h @@ -0,0 +1,73 @@ +/* wmem_stack.h + * 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 0000000000..0959105644 --- /dev/null +++ b/wsutil/wmem/wmem_strbuf.c @@ -0,0 +1,308 @@ +/* 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 +#include +#include +#include + +#include "wmem-int.h" +#include "wmem_core.h" +#include "wmem_strbuf.h" + +#define DEFAULT_MINIMUM_LEN 16 + +/* 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_len is the length of the raw buffer pointed to by str, regardless of + * what string is actually being stored (i.e. the buffer contents) + * max_len is the maximum permitted alloc_len (NOT the maximum permitted len, + * which must be one shorter than alloc_len to permit null-termination). + * When max_len is 0 (the default), no maximum is enforced. + */ +struct _wmem_strbuf_t { + wmem_allocator_t *allocator; + + gchar *str; + + gsize len; + gsize alloc_len; + gsize max_len; +}; + +/* _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_len - (S)->len - 1) +#define WMEM_STRBUF_RAW_ROOM(S) ((S)->alloc_len - (S)->len) + +wmem_strbuf_t * +wmem_strbuf_sized_new(wmem_allocator_t *allocator, + gsize alloc_len, gsize max_len) +{ + wmem_strbuf_t *strbuf; + + ASSERT((max_len == 0) || (alloc_len <= max_len)); + + strbuf = wmem_new(allocator, wmem_strbuf_t); + + strbuf->allocator = allocator; + strbuf->len = 0; + strbuf->alloc_len = alloc_len ? alloc_len : DEFAULT_MINIMUM_LEN; + strbuf->max_len = max_len; + + strbuf->str = (gchar *)wmem_alloc(strbuf->allocator, strbuf->alloc_len); + strbuf->str[0] = '\0'; + + return strbuf; +} + +wmem_strbuf_t * +wmem_strbuf_new(wmem_allocator_t *allocator, const gchar *str) +{ + wmem_strbuf_t *strbuf; + gsize len, alloc_len; + + len = str ? strlen(str) : 0; + alloc_len = DEFAULT_MINIMUM_LEN; + + /* +1 for the null-terminator */ + while (alloc_len < (len + 1)) { + alloc_len *= 2; + } + + strbuf = wmem_strbuf_sized_new(allocator, alloc_len, 0); + + if (str && len > 0) { + (void) g_strlcpy(strbuf->str, str, alloc_len); + strbuf->len = len; + } + + return strbuf; +} + +/* grows the allocated size of the wmem_strbuf_t. If max_len is set, then + * not guaranteed to grow by the full amount to_add */ +static inline void +wmem_strbuf_grow(wmem_strbuf_t *strbuf, const gsize to_add) +{ + gsize 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_len; + new_len = strbuf->len + to_add; + + /* +1 for the null-terminator */ + while (new_alloc_len < (new_len + 1)) { + new_alloc_len *= 2; + } + + /* max length only enforced if not 0 */ + if (strbuf->max_len && new_alloc_len > strbuf->max_len) { + new_alloc_len = strbuf->max_len; + } + + if (new_alloc_len == strbuf->alloc_len) { + return; + } + + strbuf->str = (gchar *)wmem_realloc(strbuf->allocator, strbuf->str, new_alloc_len); + + strbuf->alloc_len = new_alloc_len; +} + +void +wmem_strbuf_append(wmem_strbuf_t *strbuf, const gchar *str) +{ + gsize append_len; + + if (!str || str[0] == '\0') { + return; + } + + append_len = strlen(str); + + wmem_strbuf_grow(strbuf, append_len); + + (void) g_strlcpy(&strbuf->str[strbuf->len], str, strbuf->max_len ? WMEM_STRBUF_RAW_ROOM(strbuf) : append_len+1); + + strbuf->len = MIN(strbuf->len + append_len, strbuf->alloc_len - 1); +} + +void +wmem_strbuf_append_len(wmem_strbuf_t *strbuf, const gchar *str, gsize append_len) +{ + + if (!append_len || !str) { + return; + } + + wmem_strbuf_grow(strbuf, append_len); + + if (strbuf->max_len) { + append_len = MIN(append_len, WMEM_STRBUF_ROOM(strbuf)); + } + + 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, gboolean reset) +{ + 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; + } + + /* No space in buffer, output was truncated. */ + if (reset) { + strbuf->str[strbuf->len] = '\0'; /* Reset. */ + } + else { + strbuf->len += buffer_size - 1; /* Append. */ + ASSERT(strbuf->len == strbuf->alloc_len - 1); + } + + 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 gchar *fmt, va_list ap) +{ + int want_len; + va_list ap2; + + G_VA_COPY(ap2, ap); + /* Try to write buffer, check if output fits. */ + want_len = _strbuf_vsnprintf(strbuf, fmt, ap2, TRUE); /* Remove output if truncated. */ + va_end(ap2); + if (want_len <= 0) + return; + + /* Resize buffer and try again. This could hit the 'max_len' ceiling. */ + wmem_strbuf_grow(strbuf, want_len); + _strbuf_vsnprintf(strbuf, fmt, ap, FALSE); /* Keep output if truncated. */ +} + +void +wmem_strbuf_append_printf(wmem_strbuf_t *strbuf, const gchar *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 gchar c) +{ + wmem_strbuf_grow(strbuf, 1); + + if (!strbuf->max_len || WMEM_STRBUF_ROOM(strbuf) >= 1) { + strbuf->str[strbuf->len] = c; + strbuf->len++; + strbuf->str[strbuf->len] = '\0'; + } +} + +void +wmem_strbuf_append_unichar(wmem_strbuf_t *strbuf, const gunichar c) +{ + gchar buf[6]; + gsize charlen; + + charlen = g_unichar_to_utf8(c, buf); + + wmem_strbuf_grow(strbuf, charlen); + + if (!strbuf->max_len || WMEM_STRBUF_ROOM(strbuf) >= charlen) { + memcpy(&strbuf->str[strbuf->len], buf, charlen); + strbuf->len += charlen; + strbuf->str[strbuf->len] = '\0'; + } +} + +void +wmem_strbuf_truncate(wmem_strbuf_t *strbuf, const gsize len) +{ + if (len >= strbuf->len) { + return; + } + + strbuf->str[len] = '\0'; + strbuf->len = len; +} + +const gchar * +wmem_strbuf_get_str(wmem_strbuf_t *strbuf) +{ + return strbuf->str; +} + +gsize +wmem_strbuf_get_len(wmem_strbuf_t *strbuf) +{ + return strbuf->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) +{ + char *ret; + + ret = (char *)wmem_realloc(strbuf->allocator, strbuf->str, strbuf->len+1); + + wmem_free(strbuf->allocator, strbuf); + + return ret; +} + +/* + * 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 0000000000..d2f4b3bb2e --- /dev/null +++ b/wsutil/wmem/wmem_strbuf.h @@ -0,0 +1,120 @@ +/* wmem_strbuf.h + * 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 + +#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. + * + * @{ + */ + +struct _wmem_strbuf_t; + +typedef struct _wmem_strbuf_t wmem_strbuf_t; + +WS_DLL_PUBLIC +wmem_strbuf_t * +wmem_strbuf_sized_new(wmem_allocator_t *allocator, + gsize alloc_len, gsize max_len) +G_GNUC_MALLOC; + +#define wmem_strbuf_new_label(ALLOCATOR) \ + wmem_strbuf_sized_new((ALLOCATOR), 0, ITEM_LABEL_LENGTH) + +WS_DLL_PUBLIC +wmem_strbuf_t * +wmem_strbuf_new(wmem_allocator_t *allocator, const gchar *str) +G_GNUC_MALLOC; + +WS_DLL_PUBLIC +void +wmem_strbuf_append(wmem_strbuf_t *strbuf, const gchar *str); + +/* Appends up to append_len bytes (as allowed by strbuf->max_len) 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 gchar *str, gsize append_len); + +WS_DLL_PUBLIC +void +wmem_strbuf_append_printf(wmem_strbuf_t *strbuf, const gchar *format, ...) +G_GNUC_PRINTF(2, 3); + +WS_DLL_PUBLIC +void +wmem_strbuf_append_vprintf(wmem_strbuf_t *strbuf, const gchar *fmt, va_list ap); + +WS_DLL_PUBLIC +void +wmem_strbuf_append_c(wmem_strbuf_t *strbuf, const gchar c); + +WS_DLL_PUBLIC +void +wmem_strbuf_append_unichar(wmem_strbuf_t *strbuf, const gunichar c); + +WS_DLL_PUBLIC +void +wmem_strbuf_truncate(wmem_strbuf_t *strbuf, const gsize len); + +WS_DLL_PUBLIC +const gchar * +wmem_strbuf_get_str(wmem_strbuf_t *strbuf); + +WS_DLL_PUBLIC +gsize +wmem_strbuf_get_len(wmem_strbuf_t *strbuf); + +/** 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); + +/** @} + * @} */ + +#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 0000000000..33012d779d --- /dev/null +++ b/wsutil/wmem/wmem_strutl.c @@ -0,0 +1,337 @@ +/* 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 + */ + +#include "config.h" + +#include +#include + +#ifdef _WIN32 +#include +#endif + +#include +#include + +#include "wmem_core.h" +#include "wmem_allocator.h" +#include "wmem_strutl.h" + +gchar * +wmem_strdup(wmem_allocator_t *allocator, const gchar *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 (gchar *)memcpy(wmem_alloc(allocator, len), src, len); +} + +gchar * +wmem_strndup(wmem_allocator_t *allocator, const gchar *src, const size_t len) +{ + gchar *dst; + guint i; + + dst = (gchar *)wmem_alloc(allocator, len+1); + + for (i=0; (i < len) && src[i]; i++) { + dst[i] = src[i]; + } + + dst[i] = '\0'; + + return dst; +} + +gchar * +wmem_strdup_printf(wmem_allocator_t *allocator, const gchar *fmt, ...) +{ + va_list ap; + gchar *dst; + + va_start(ap, fmt); + dst = wmem_strdup_vprintf(allocator, fmt, ap); + va_end(ap); + + return dst; +} + +/* + * Using g_printf_string_upper_bound() to find the needed length almost doubles + * the execution time of this function. Instead we use a pre allocated buffer + * which may waste a bit of memory but are faster. As this is mostly called with + * packet scoped memory(?) that shouldn't matter that much. + * In my test file all strings was less than 72 characters long and quite a few + * over 68 characters long. Chose 80 as the default. + */ +#ifndef _WIN32 +#define WMEM_STRDUP_VPRINTF_DEFAULT_BUFFER 80 +gchar * +wmem_strdup_vprintf(wmem_allocator_t *allocator, const gchar *fmt, va_list ap) +{ + va_list ap2; + gchar *dst; + int needed_len; + + G_VA_COPY(ap2, ap); + + /* needed_len = g_printf_string_upper_bound(fmt, ap2); */ + + dst = (gchar *)wmem_alloc(allocator, WMEM_STRDUP_VPRINTF_DEFAULT_BUFFER); + + /* Returns: the number of characters which would be produced if the buffer was large enough + * (not including the null, for which we add +1 ourselves). */ + needed_len = g_vsnprintf(dst, (gulong) WMEM_STRDUP_VPRINTF_DEFAULT_BUFFER, fmt, ap2) + 1; + va_end(ap2); + + if (needed_len > WMEM_STRDUP_VPRINTF_DEFAULT_BUFFER) { + wmem_free(allocator, dst); + dst = (gchar *)wmem_alloc(allocator, needed_len); + G_VA_COPY(ap2, ap); + g_vsnprintf(dst, (gulong) needed_len, fmt, ap2); + va_end(ap2); + } + + return dst; +} +#else /* _WIN32 */ +/* + * GLib's v*printf routines are surprisingly slow on Windows, at least with + * GLib 2.40.0. This appears to be due to GLib using the gnulib version of + * vasnprintf when compiled under MinGW. If GLib ever ends up using the + * native Windows v*printf routines this can be removed. + */ +gchar * +wmem_strdup_vprintf(wmem_allocator_t *allocator, const gchar *fmt, va_list ap) +{ + va_list ap2; + gchar *dst; + int needed_len; + + G_VA_COPY(ap2, ap); + + needed_len = _vscprintf(fmt, ap2) + 1; + + dst = (gchar *)wmem_alloc(allocator, needed_len); + + vsprintf_s(dst, needed_len, fmt, ap2); + + va_end(ap2); + + return dst; +} +#endif /* _WIN32 */ + +gchar * +wmem_strconcat(wmem_allocator_t *allocator, const gchar *first, ...) +{ + gsize len; + va_list args; + gchar *s; + gchar *concat; + gchar *ptr; + + if (!first) + return NULL; + + len = 1 + strlen(first); + va_start(args, first); + while ((s = va_arg(args, gchar*))) { + len += strlen(s); + } + va_end(args); + + ptr = concat = (gchar *)wmem_alloc(allocator, len); + + ptr = g_stpcpy(ptr, first); + va_start(args, first); + while ((s = va_arg(args, gchar*))) { + ptr = g_stpcpy(ptr, s); + } + va_end(args); + + return concat; +} + +gchar * +wmem_strjoin(wmem_allocator_t *allocator, + const gchar *separator, const gchar *first, ...) +{ + gsize len; + va_list args; + gsize separator_len; + gchar *s; + gchar *concat; + gchar *ptr; + + if (!first) + return NULL; + + if (separator == NULL) { + separator = ""; + } + + separator_len = strlen (separator); + + len = 1 + strlen(first); /* + 1 for null byte */ + va_start(args, first); + while ((s = va_arg(args, gchar*))) { + len += (separator_len + strlen(s)); + } + va_end(args); + + ptr = concat = (gchar *)wmem_alloc(allocator, len); + ptr = g_stpcpy(ptr, first); + va_start(args, first); + while ((s = va_arg(args, gchar*))) { + ptr = g_stpcpy(ptr, separator); + ptr = g_stpcpy(ptr, s); + } + va_end(args); + + return concat; + +} + +gchar * +wmem_strjoinv(wmem_allocator_t *allocator, + const gchar *separator, gchar **str_array) +{ + gchar *string = NULL; + + if (!str_array) + return NULL; + + if (separator == NULL) { + separator = ""; + } + + if (str_array[0]) { + gint i; + gchar *ptr; + gsize len, separator_len; + + separator_len = strlen(separator); + + /* Get first part of length. Plus one for null byte. */ + len = 1 + strlen(str_array[0]); + /* Get the full length, including the separators. */ + for (i = 1; str_array[i] != NULL; i++) { + len += separator_len; + len += strlen(str_array[i]); + } + + /* Allocate and build the string. */ + string = (gchar *)wmem_alloc(allocator, len); + ptr = g_stpcpy(string, str_array[0]); + for (i = 1; str_array[i] != NULL; i++) { + ptr = g_stpcpy(ptr, separator); + ptr = g_stpcpy(ptr, str_array[i]); + } + } + + return string; + +} + +gchar ** +wmem_strsplit(wmem_allocator_t *allocator, const gchar *src, + const gchar *delimiter, int max_tokens) +{ + gchar *splitted; + gchar *s; + guint tokens; + guint sep_len; + guint i; + gchar **vec; + + if (!src || !delimiter || !delimiter[0]) + return NULL; + + /* An empty string results in an empty vector. */ + if (!src[0]) { + vec = wmem_new0(allocator, gchar *); + return vec; + } + + splitted = wmem_strdup(allocator, src); + sep_len = (guint)strlen(delimiter); + + if (max_tokens < 1) + max_tokens = INT_MAX; + + /* Calculate the number of fields. */ + s = splitted; + tokens = 1; + while (tokens < (guint)max_tokens && (s = strstr(s, delimiter))) { + s += sep_len; + tokens++; + } + + vec = wmem_alloc_array(allocator, gchar *, tokens + 1); + + /* Populate the array of string tokens. */ + s = splitted; + vec[0] = s; + tokens = 1; + while (tokens < (guint)max_tokens && (s = strstr(s, delimiter))) { + for (i = 0; i < sep_len; i++) + s[i] = '\0'; + s += sep_len; + vec[tokens] = s; + tokens++; + + } + + vec[tokens] = NULL; + + return vec; +} + +/* + * wmem_ascii_strdown: + * based on g_ascii_strdown. + */ +gchar* +wmem_ascii_strdown(wmem_allocator_t *allocator, const gchar *str, gssize len) +{ + gchar *result, *s; + + g_return_val_if_fail (str != NULL, NULL); + + if (len < 0) + len = strlen (str); + + result = wmem_strndup(allocator, str, len); + for (s = result; *s; s++) + *s = g_ascii_tolower (*s); + + return result; +} +/* + * 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 0000000000..87963a77b3 --- /dev/null +++ b/wsutil/wmem/wmem_strutl.h @@ -0,0 +1,124 @@ +/* wmem_strutl.h + * 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 + +#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 +gchar * +wmem_strdup(wmem_allocator_t *allocator, const gchar *src) +G_GNUC_MALLOC; + +WS_DLL_PUBLIC +gchar * +wmem_strndup(wmem_allocator_t *allocator, const gchar *src, const size_t len) +G_GNUC_MALLOC; + +WS_DLL_PUBLIC +gchar * +wmem_strdup_printf(wmem_allocator_t *allocator, const gchar *fmt, ...) +G_GNUC_MALLOC G_GNUC_PRINTF(2, 3); + +WS_DLL_PUBLIC +gchar * +wmem_strdup_vprintf(wmem_allocator_t *allocator, const gchar *fmt, va_list ap) +G_GNUC_MALLOC; + +WS_DLL_PUBLIC +gchar * +wmem_strconcat(wmem_allocator_t *allocator, const gchar *first, ...) +G_GNUC_MALLOC G_GNUC_NULL_TERMINATED; + +WS_DLL_PUBLIC +gchar * +wmem_strjoin(wmem_allocator_t *allocator, + const gchar *separator, const gchar *first, ...) +G_GNUC_MALLOC G_GNUC_NULL_TERMINATED; + +WS_DLL_PUBLIC +gchar * +wmem_strjoinv(wmem_allocator_t *allocator, + const gchar *separator, gchar **str_array) +G_GNUC_MALLOC; + +/** + * Splits a string into a maximum of max_tokens pieces, using the given + * delimiter. If max_tokens is reached, the remainder of string is appended + * to the last token. Successive tokens are not folded and will instead result + * in an empty string as element. + * + * If src or delimiter are NULL, or if delimiter is empty, this will return + * NULL. + * + * Do not use with a NULL allocator, use g_strsplit instead. + */ +WS_DLL_PUBLIC +gchar ** +wmem_strsplit(wmem_allocator_t *allocator, const gchar *src, + const gchar *delimiter, int max_tokens); + + +/** + * wmem_ascii_strdown: + * Based on g_ascii_strdown + * @param allocator An enumeration of the different types of available allocators. + * @param str a string. + * @param len length of str in bytes, or -1 if str is nul-terminated. + * + * Converts all upper case ASCII letters to lower case ASCII letters. + * + * Return value: a newly-allocated string, with all the upper case + * characters in str converted to lower case, with + * semantics that exactly match g_ascii_tolower(). (Note + * that this is unlike the old g_strdown(), which modified + * the string in place.) + **/ +WS_DLL_PUBLIC +gchar* +wmem_ascii_strdown(wmem_allocator_t *allocator, const gchar *str, gssize 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 0000000000..bceb906bd7 --- /dev/null +++ b/wsutil/wmem/wmem_test.c @@ -0,0 +1,1485 @@ +/* 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 gchar * +wmem_test_rand_string(wmem_allocator_t *allocator, gint minlen, gint maxlen) +{ + gchar *str; + gint len, i; + + len = g_random_int_range(minlen, maxlen); + + /* +1 for null-terminator */ + str = (gchar*)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); + + new_str = wmem_strconcat(allocator, "ABC", NULL); + g_assert_cmpstr(new_str, ==, "ABC"); + new_str = wmem_strconcat(allocator, "ABC", "DEF", NULL); + g_assert_cmpstr(new_str, ==, "ABCDEF"); + wmem_strict_check_canaries(allocator); + new_str = wmem_strconcat(allocator, "", "", "ABCDEF", "", "GH", NULL); + g_assert_cmpstr(new_str, ==, "ABCDEFGH"); + wmem_strict_check_canaries(allocator); + + split_str = wmem_strsplit(allocator, "A-C", "-", 2); + g_assert_cmpstr(split_str[0], ==, "A"); + g_assert_cmpstr(split_str[1], ==, "C"); + g_assert_true(split_str[2] == NULL); + split_str = wmem_strsplit(allocator, "A-C", "-", 0); + g_assert_cmpstr(split_str[0], ==, "A"); + g_assert_cmpstr(split_str[1], ==, "C"); + g_assert_true(split_str[2] == NULL); + split_str = wmem_strsplit(allocator, "--aslkf-asio--asfj-as--", "-", 10); + g_assert_cmpstr(split_str[0], ==, ""); + g_assert_cmpstr(split_str[1], ==, ""); + g_assert_cmpstr(split_str[2], ==, "aslkf"); + g_assert_cmpstr(split_str[3], ==, "asio"); + g_assert_cmpstr(split_str[4], ==, ""); + g_assert_cmpstr(split_str[5], ==, "asfj"); + g_assert_cmpstr(split_str[6], ==, "as"); + g_assert_cmpstr(split_str[7], ==, ""); + g_assert_cmpstr(split_str[8], ==, ""); + g_assert_true(split_str[9] == NULL); + split_str = wmem_strsplit(allocator, "--aslkf-asio--asfj-as--", "-", 5); + g_assert_cmpstr(split_str[0], ==, ""); + g_assert_cmpstr(split_str[1], ==, ""); + g_assert_cmpstr(split_str[2], ==, "aslkf"); + g_assert_cmpstr(split_str[3], ==, "asio"); + g_assert_cmpstr(split_str[4], ==, "-asfj-as--"); + g_assert_true(split_str[5] == NULL); + split_str = wmem_strsplit(allocator, "", "-", -1); + g_assert_true(split_str[0] == NULL); + wmem_strict_check_canaries(allocator); + + orig_str = "TeStAsCiIsTrDoWn"; + new_str = wmem_ascii_strdown(allocator, orig_str, -1); + g_assert_cmpstr(new_str, ==, "testasciistrdown"); + + 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 --verbose" to see results. */ +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_STRICT); + + 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); + +#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 + + 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_strconcat(s_val, s_val, NULL); + } + RESOURCE_USAGE_END; + g_test_minimized_result(utime_ms + stime_ms, + "g_strconcat 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]); + } + + RESOURCE_USAGE_START; + for (i = 0; i < LOOP_COUNT; i++) { + str_ptr[i] = g_strconcat(s_val, s_val, s_val, s_val, s_val, NULL); + } + RESOURCE_USAGE_END; + g_test_minimized_result(utime_ms + stime_ms, + "g_strconcat 5 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++) { + wmem_strdup_printf(allocator, "%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); + + RESOURCE_USAGE_START; + for (i = 0; i < LOOP_COUNT; i++) { + wmem_strconcat(allocator, s_val, s_val, NULL); + } + RESOURCE_USAGE_END; + g_test_minimized_result(utime_ms + stime_ms, + "wmem_strconcat 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 5 strings: u %.3f ms s %.3f ms", utime_ms, stime_ms); + + RESOURCE_USAGE_START; + for (i = 0; i < LOOP_COUNT; i++) { + wmem_strconcat(allocator, s_val, s_val, s_val, s_val, s_val, NULL); + } + RESOURCE_USAGE_END; + g_test_minimized_result(utime_ms + stime_ms, + "wmem_strconcat 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; + guint32 val, *buf; + guint32 vals[8]; + guint32 *raw; + guint32 lastint; + + allocator = wmem_allocator_new(WMEM_ALLOCATOR_STRICT); + + array = wmem_array_new(allocator, sizeof(guint32)); + 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; + char *str; + + 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_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); + + strbuf = wmem_strbuf_sized_new(allocator, 10, 10); + g_assert_true(strbuf); + g_assert_cmpstr(wmem_strbuf_get_str(strbuf), ==, ""); + g_assert_cmpuint(wmem_strbuf_get_len(strbuf), ==, 0); + + wmem_strbuf_append(strbuf, "FUZZ"); + g_assert_cmpstr(wmem_strbuf_get_str(strbuf), ==, "FUZZ"); + g_assert_cmpuint(wmem_strbuf_get_len(strbuf), ==, 4); + + wmem_strbuf_append_printf(strbuf, "%d%s", 3, "abcdefghijklmnop"); + g_assert_cmpstr(wmem_strbuf_get_str(strbuf), ==, "FUZZ3abcd"); + g_assert_cmpuint(wmem_strbuf_get_len(strbuf), ==, 9); + + wmem_strbuf_append(strbuf, "abcdefghijklmnopqrstuvwxyz"); + g_assert_cmpstr(wmem_strbuf_get_str(strbuf), ==, "FUZZ3abcd"); + g_assert_cmpuint(wmem_strbuf_get_len(strbuf), ==, 9); + + wmem_strbuf_append_c(strbuf, 'q'); + g_assert_cmpstr(wmem_strbuf_get_str(strbuf), ==, "FUZZ3abcd"); + g_assert_cmpuint(wmem_strbuf_get_len(strbuf), ==, 9); + + wmem_strbuf_append_unichar(strbuf, g_utf8_get_char("\xC2\xA9")); + g_assert_cmpstr(wmem_strbuf_get_str(strbuf), ==, "FUZZ3abcd"); + g_assert_cmpuint(wmem_strbuf_get_len(strbuf), ==, 9); + + str = wmem_strbuf_finalize(strbuf); + g_assert_cmpstr(str, ==, "FUZZ3abcd"); + g_assert_cmpuint(strlen(str), ==, 9); + + 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_tree(void) +{ + wmem_allocator_t *allocator, *extra_allocator; + wmem_tree_t *tree; + guint32 i; + int seen_values = 0; + int j; + gchar *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 gboolean +wmem_test_overlap(guint64 low, guint64 high, guint64 lowbis, guint64 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; + gint32 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 G_MAXINT32 as a max because of the type returned by + g_test_rand_int_range. + */ + max_rand = G_MAXINT32; + r2.max_edge = range.max_edge = 0; + range.low = g_test_rand_int_range(0, max_rand); + range.high = g_test_rand_int_range( (gint32)range.low, (gint32)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; + gboolean is_subtree; + gboolean 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; + guint metadata_scope_cb_id; + guint 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; + +gboolean +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 0000000000..4c8f10a1a0 --- /dev/null +++ b/wsutil/wmem/wmem_tree.c @@ -0,0 +1,838 @@ +/* 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 gboolean +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 gboolean +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, gboolean free_keys, gboolean 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, gboolean free_keys, gboolean 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); +} + +gboolean +wmem_tree_is_empty(wmem_tree_t *tree) +{ + return tree->root == NULL; +} + +static gboolean +count_nodes(const void *key _U_, void *value _U_, void *userdata) +{ + guint* count = (guint*)userdata; + (*count)++; + return FALSE; +} + +guint +wmem_tree_count(wmem_tree_t* tree) +{ + guint 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, gboolean 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, guint32 key, + void*(*func)(void*), void* data, gboolean is_subtree, gboolean 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, guint32 key, + void*(*func)(void*), void* data, gboolean is_subtree, gboolean 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, guint32 key, void *data) +{ + lookup_or_insert32(tree, key, NULL, data, FALSE, TRUE); +} + +void * +wmem_tree_lookup32(wmem_tree_t *tree, guint32 key) +{ + 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, guint32 key) +{ + 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, guint32 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 gchar* k, void* v, guint32 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 gchar* k, guint32 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 gchar* k, guint32 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; + guint32 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]; + } + } + + 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*, guint32)) +{ + wmem_tree_t *lookup_tree = NULL; + wmem_tree_key_t *cur_key; + guint32 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 */ + 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 gboolean +wmem_tree_foreach_nodes(wmem_tree_node_t* node, wmem_foreach_func callback, + void *user_data) +{ + gboolean 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; +} + +gboolean +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, guint32 level, wmem_printer_func key_printer, wmem_printer_func data_printer); + +static void +wmem_print_indent(guint32 level) { + guint32 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, guint32 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 0000000000..51f3c9908b --- /dev/null +++ b/wsutil/wmem/wmem_tree.h @@ -0,0 +1,255 @@ +/* wmem_tree.h + * 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, gboolean free_keys, gboolean free_values); + +/** Returns true if the tree is empty (has no nodes). */ +WS_DLL_PUBLIC +gboolean +wmem_tree_is_empty(wmem_tree_t *tree); + +/** Returns number of nodes in tree */ +WS_DLL_PUBLIC +guint +wmem_tree_count(wmem_tree_t* tree); + +/** Insert a node indexed by a guint32 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, guint32 key, void *data); + +/** Look up a node in the tree indexed by a guint32 integer value. If no node is + * found the function will return NULL. + */ +WS_DLL_PUBLIC +void * +wmem_tree_lookup32(wmem_tree_t *tree, guint32 key); + +/** Look up a node in the tree indexed by a guint32 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, guint32 key); + +/** Remove a node in the tree indexed by a guint32 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, guint32 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 guint32. 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 gchar* key, void *data, + guint32 flags); + +/** Lookup the value under a string key, like wmem_tree_lookup32 but where the + * keye is a null-terminated string instead of a guint32. See + * wmem_tree_insert_string for an explanation of flags. */ +WS_DLL_PUBLIC +void * +wmem_tree_lookup_string(wmem_tree_t* tree, const gchar* key, guint32 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 gchar* key, guint32 flags); + +typedef struct _wmem_tree_key_t { + guint32 length; /**< length in guint32 words */ + guint32 *key; +} wmem_tree_key_t; + +/** Insert a node indexed by a sequence of guint32 key values. + * + * Takes as key an array of guint32 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 guint32 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 guint32 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 guint32 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 gboolean (*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 +gboolean +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) */ +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 0000000000..c9b02c2e17 --- /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; + guint 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; + gboolean 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; + } + } +} + +guint +wmem_register_callback(wmem_allocator_t *allocator, + wmem_user_cb_t callback, void *user_data) +{ + wmem_user_cb_container_t *container; + static guint 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, guint 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 0000000000..e107dcdaa9 --- /dev/null +++ b/wsutil/wmem/wmem_user_cb.h @@ -0,0 +1,92 @@ +/* wmem_user_cb.h + * 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 gboolean (*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 +guint +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, guint 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 0000000000..3fed11e354 --- /dev/null +++ b/wsutil/wmem/wmem_user_cb_int.h @@ -0,0 +1,44 @@ +/* wmem_user_cb_int.h + * 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