wsutil/wmem/wmem_allocator_block_fast.c

   1 /* wmem_allocator_block.c
   2  * Wireshark Memory Manager Fast Large-Block Allocator
   3  *
   4  * Wireshark - Network traffic analyzer
   5  * By Gerald Combs <gerald@wireshark.org>
   6  * Copyright 1998 Gerald Combs
   7  *
   8  * SPDX-License-Identifier: GPL-2.0-or-later
   9  */
  10
  11 #include "config.h"
  12
  13 #include <stdio.h>
  14 #include <string.h>
  15
  16 #include <glib.h>
  17
  18 #include "wmem_core.h"
  19 #include "wmem_allocator.h"
  20 #include "wmem_allocator_block_fast.h"
  21
  22 /* https://mail.gnome.org/archives/gtk-devel-list/2004-December/msg00091.html
  23  * The 2*sizeof(size_t) alignment here is borrowed from GNU libc, so it should
  24  * be good most everywhere. It is more conservative than is needed on some
  25  * 64-bit platforms, but ia64 does require a 16-byte alignment. The SIMD
  26  * extensions for x86 and ppc32 would want a larger alignment than this, but
  27  * we don't need to do better than malloc.
  28  */
  29 #define WMEM_ALIGN_AMOUNT (2 * sizeof (size_t))
  30 #define WMEM_ALIGN_SIZE(SIZE) ((~(WMEM_ALIGN_AMOUNT-1)) & \
  31         ((SIZE) + (WMEM_ALIGN_AMOUNT-1)))
  32
  33 #define WMEM_CHUNK_TO_DATA(CHUNK) ((void*)((uint8_t*)(CHUNK) + WMEM_CHUNK_HEADER_SIZE))
  34 #define WMEM_DATA_TO_CHUNK(DATA) ((wmem_block_fast_chunk_t*)((uint8_t*)(DATA) - WMEM_CHUNK_HEADER_SIZE))
  35
  36 #define WMEM_BLOCK_MAX_ALLOC_SIZE (WMEM_BLOCK_SIZE - (WMEM_BLOCK_HEADER_SIZE + WMEM_CHUNK_HEADER_SIZE))
  37
  38 /* When required, allocate more memory from the OS in chunks of this size.
  39  * 2MB is a pretty arbitrary value - it's big enough that it should last a while
  40  * and small enough that a mostly-unused one doesn't waste *too* much. It's
  41  * also a nice power of two, of course. */
  42 #define WMEM_BLOCK_SIZE (2 * 1024 * 1024)
  43
  44 /* The header for an entire OS-level 'block' of memory */
  45 typedef struct _wmem_block_fast_hdr {
  46     struct _wmem_block_fast_hdr *next;
  47
  48     int32_t pos;
  49 } wmem_block_fast_hdr_t;
  50 #define WMEM_BLOCK_HEADER_SIZE WMEM_ALIGN_SIZE(sizeof(wmem_block_fast_hdr_t))
  51
  52 typedef struct {
  53     uint32_t len;
  54 } wmem_block_fast_chunk_t;
  55 #define WMEM_CHUNK_HEADER_SIZE WMEM_ALIGN_SIZE(sizeof(wmem_block_fast_chunk_t))
  56
  57 #define JUMBO_MAGIC 0xFFFFFFFF
  58 typedef struct _wmem_block_fast_jumbo {
  59     struct _wmem_block_fast_jumbo *prev, *next;
  60 } wmem_block_fast_jumbo_t;
  61 #define WMEM_JUMBO_HEADER_SIZE WMEM_ALIGN_SIZE(sizeof(wmem_block_fast_jumbo_t))
  62
  63 typedef struct {
  64     wmem_block_fast_hdr_t   *block_list;
  65     wmem_block_fast_jumbo_t *jumbo_list;
  66 } wmem_block_fast_allocator_t;
  67
  68 /* Creates a new block, and initializes it. */
  69 static inline void
  70 wmem_block_fast_new_block(wmem_block_fast_allocator_t *allocator)
  71 {
  72     wmem_block_fast_hdr_t *block;
  73
  74     /* allocate/initialize the new block and add it to the block list */
  75     block = (wmem_block_fast_hdr_t *)wmem_alloc(NULL, WMEM_BLOCK_SIZE);
  76
  77     block->pos  = WMEM_BLOCK_HEADER_SIZE;
  78     block->next = allocator->block_list;
  79
  80     allocator->block_list = block;
  81 }
  82
  83 /* API */
  84
  85 static void *
  86 wmem_block_fast_alloc(void *private_data, const size_t size)
  87 {
  88     wmem_block_fast_allocator_t *allocator = (wmem_block_fast_allocator_t*) private_data;
  89     wmem_block_fast_chunk_t     *chunk;
  90     int32_t real_size;
  91
  92     if (size > WMEM_BLOCK_MAX_ALLOC_SIZE) {
  93         wmem_block_fast_jumbo_t *block;
  94
  95         /* allocate/initialize a new block of the necessary size */
  96         block = (wmem_block_fast_jumbo_t *)wmem_alloc(NULL,
  97                 size + WMEM_JUMBO_HEADER_SIZE + WMEM_CHUNK_HEADER_SIZE);
  98
  99         block->next = allocator->jumbo_list;
 100         if (block->next) {
 101             block->next->prev = block;
 102         }
 103         block->prev = NULL;
 104         allocator->jumbo_list = block;
 105
 106         chunk = ((wmem_block_fast_chunk_t*)((uint8_t*)(block) + WMEM_JUMBO_HEADER_SIZE));
 107         chunk->len = JUMBO_MAGIC;
 108
 109         return WMEM_CHUNK_TO_DATA(chunk);
 110     }
 111
 112     real_size = (int32_t)(WMEM_ALIGN_SIZE(size) + WMEM_CHUNK_HEADER_SIZE);
 113
 114     /* Allocate a new block if necessary. */
 115     if (!allocator->block_list ||
 116             (WMEM_BLOCK_SIZE - allocator->block_list->pos) < real_size) {
 117         wmem_block_fast_new_block(allocator);
 118     }
 119
 120     chunk = (wmem_block_fast_chunk_t *) ((uint8_t *) allocator->block_list + allocator->block_list->pos);
 121     /* safe to cast, size smaller than WMEM_BLOCK_MAX_ALLOC_SIZE */
 122     chunk->len = (uint32_t) size;
 123
 124     allocator->block_list->pos += real_size;
 125
 126     /* and return the user's pointer */
 127     return WMEM_CHUNK_TO_DATA(chunk);
 128 }
 129
 130 static void
 131 wmem_block_fast_free(void *private_data _U_, void *ptr _U_)
 132 {
 133    /* free is NOP */
 134 }
 135
 136 static void *
 137 wmem_block_fast_realloc(void *private_data, void *ptr, const size_t size)
 138 {
 139     wmem_block_fast_chunk_t *chunk;
 140
 141     chunk = WMEM_DATA_TO_CHUNK(ptr);
 142
 143     if (chunk->len == JUMBO_MAGIC) {
 144         wmem_block_fast_jumbo_t *block;
 145
 146         block = ((wmem_block_fast_jumbo_t*)((uint8_t*)(chunk) - WMEM_JUMBO_HEADER_SIZE));
 147         block =  (wmem_block_fast_jumbo_t*)wmem_realloc(NULL, block,
 148                 size + WMEM_JUMBO_HEADER_SIZE + WMEM_CHUNK_HEADER_SIZE);
 149         if (block->prev) {
 150             block->prev->next = block;
 151         }
 152         else {
 153             wmem_block_fast_allocator_t *allocator = (wmem_block_fast_allocator_t*) private_data;
 154             allocator->jumbo_list = block;
 155         }
 156         if (block->next) {
 157             block->next->prev = block;
 158         }
 159         return ((void*)((uint8_t*)(block) + WMEM_JUMBO_HEADER_SIZE + WMEM_CHUNK_HEADER_SIZE));
 160     }
 161     else if (chunk->len < size) {
 162         /* grow */
 163         void *newptr;
 164
 165         /* need to alloc and copy; free is no-op, so don't call it */
 166         newptr = wmem_block_fast_alloc(private_data, size);
 167         memcpy(newptr, ptr, chunk->len);
 168
 169         return newptr;
 170     }
 171
 172     /* shrink or same space - great we can do nothing */
 173     return ptr;
 174 }
 175
 176 static void
 177 wmem_block_fast_free_all(void *private_data)
 178 {
 179     wmem_block_fast_allocator_t *allocator = (wmem_block_fast_allocator_t*) private_data;
 180     wmem_block_fast_hdr_t       *cur, *nxt;
 181     wmem_block_fast_jumbo_t     *cur_jum, *nxt_jum;
 182
 183     /* iterate through the blocks, freeing all but the first and reinitializing
 184      * that one */
 185     cur = allocator->block_list;
 186
 187     if (cur) {
 188          cur->pos = WMEM_BLOCK_HEADER_SIZE;
 189          nxt = cur->next;
 190          cur->next = NULL;
 191          cur = nxt;
 192     }
 193
 194     while (cur) {
 195         nxt  = cur->next;
 196         wmem_free(NULL, cur);
 197         cur = nxt;
 198     }
 199
 200     /* now do the jumbo blocks, freeing all of them */
 201     cur_jum = allocator->jumbo_list;
 202     while (cur_jum) {
 203         nxt_jum  = cur_jum->next;
 204         wmem_free(NULL, cur_jum);
 205         cur_jum = nxt_jum;
 206     }
 207     allocator->jumbo_list = NULL;
 208 }
 209
 210 static void
 211 wmem_block_fast_gc(void *private_data _U_)
 212 {
 213     /* No-op */
 214 }
 215
 216 static void
 217 wmem_block_fast_allocator_cleanup(void *private_data)
 218 {
 219     wmem_block_fast_allocator_t *allocator = (wmem_block_fast_allocator_t*) private_data;
 220
 221     /* wmem guarantees that free_all() is called directly before this, so
 222      * simply free the first block */
 223     wmem_free(NULL, allocator->block_list);
 224
 225     /* then just free the allocator structs */
 226     wmem_free(NULL, private_data);
 227 }
 228
 229 void
 230 wmem_block_fast_allocator_init(wmem_allocator_t *allocator)
 231 {
 232     wmem_block_fast_allocator_t *block_allocator;
 233
 234     block_allocator = wmem_new(NULL, wmem_block_fast_allocator_t);
 235
 236     allocator->walloc   = &wmem_block_fast_alloc;
 237     allocator->wrealloc = &wmem_block_fast_realloc;
 238     allocator->wfree    = &wmem_block_fast_free;
 239
 240     allocator->free_all = &wmem_block_fast_free_all;
 241     allocator->gc       = &wmem_block_fast_gc;
 242     allocator->cleanup  = &wmem_block_fast_allocator_cleanup;
 243
 244     allocator->private_data = (void*) block_allocator;
 245
 246     block_allocator->block_list = NULL;
 247     block_allocator->jumbo_list = NULL;
 248 }
 249
 250 /*
 251  * Editor modelines  -  https://www.wireshark.org/tools/modelines.html
 252  *
 253  * Local variables:
 254  * c-basic-offset: 4
 255  * tab-width: 8
 256  * indent-tabs-mode: nil
 257  * End:
 258  *
 259  * vi: set shiftwidth=4 tabstop=8 expandtab:
 260  * :indentSize=4:tabSize=8:noTabs=true:
 261  */