firmware/buflib.c

   1 /***************************************************************************
   2 *             __________               __   ___.
   3 *   Open      \______   \ ____   ____ |  | _\_ |__   _______  ___
   4 *   Source     |       _//  _ \_/ ___\|  |/ /| __ \ /  _ \  \/  /
   5 *   Jukebox    |    |   (  <_> )  \___|    < | \_\ (  <_> > <  <
   6 *   Firmware   |____|_  /\____/ \___  >__|_ \|___  /\____/__/\_ \
   7 *                     \/            \/     \/    \/            \/
   8 * $Id$
   9 *
  10 * This is a memory allocator designed to provide reasonable management of free
  11 * space and fast access to allocated data. More than one allocator can be used
  12 * at a time by initializing multiple contexts.
  13 *
  14 * Copyright (C) 2009 Andrew Mahone
  15 * Copyright (C) 2011 Thomas Martitz
  16 *
  17 *
  18 * This program is free software; you can redistribute it and/or
  19 * modify it under the terms of the GNU General Public License
  20 * as published by the Free Software Foundation; either version 2
  21 * of the License, or (at your option) any later version.
  22 *
  23 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
  24 * KIND, either express or implied.
  25 *
  26 ****************************************************************************/
  27
  28 #include <stdlib.h> /* for abs() */
  29 #include <stdio.h> /* for snprintf() */
  30 #include "buflib.h"
  31 #include "string-extra.h" /* strlcpy() */
  32 #include "debug.h"
  33 #include "buffer.h"
  34 #include "system.h" /* for ALIGN_*() */
  35
  36 /* The main goal of this design is fast fetching of the pointer for a handle.
  37  * For that reason, the handles are stored in a table at the end of the buffer
  38  * with a fixed address, so that returning the pointer for a handle is a simple
  39  * table lookup. To reduce the frequency with which allocated blocks will need
  40  * to be moved to free space, allocations grow up in address from the start of
  41  * the buffer. The buffer is treated as an array of union buflib_data. Blocks
  42  * start with a length marker, which is included in their length. Free blocks
  43  * are marked by negative length. Allocated blocks have a positiv length marker,
  44  * and additional metadata forllowing that: It follows a pointer
  45  * (union buflib_data*) to the corresponding handle table entry. so that it can
  46  * be quickly found and updated during compaction. After that follows
  47  * the pointer to the struct buflib_callbacks associated with this allocation
  48  * (may be NULL). That pointer follows a variable length character array
  49  * containing the nul-terminated string identifier of the allocation. After this
  50  * array there's a length marker for the length of the character array including
  51  * this length marker (counted in n*sizeof(union buflib_data)), which allows
  52  * to find the start of the character array (and therefore the start of the
  53  * entire block) when only the handle or payload start is known.
  54  *
  55  * Example:
  56  * |<- alloc block #1 ->|<- unalloc block ->|<- alloc block #2      ->|<-handle table->|
  57  * |L|H|C|cccc|L2|XXXXXX|-L|YYYYYYYYYYYYYYYY|L|H|C|cc|L2|XXXXXXXXXXXXX|AAA|
  58  *
  59  * L - length marker (negative if block unallocated)
  60  * H - handle table enry pointer
  61  * C - pointer to struct buflib_callbacks
  62  * c - variable sized string identifier
  63  * L2 - second length marker for string identifier
  64  * X - actual payload
  65  * Y - unallocated space
  66  *
  67  * A - pointer to start of payload (first X) in the handle table (may be null)
  68  *
  69  * The blocks can be walked by jumping the abs() of the L length marker, i.e.
  70  * union buflib_data* L;
  71  * for(L = start; L < end; L += abs(L->val)) { .... }
  72  *
  73  *
  74  * The allocator functions are passed a context struct so that two allocators
  75  * can be run, for example, one per core may be used, with convenience wrappers
  76  * for the single-allocator case that use a predefined context.
  77  */
  78
  79 #define B_ALIGN_DOWN(x) \
  80     ALIGN_DOWN(x, sizeof(union buflib_data))
  81
  82 #define B_ALIGN_UP(x) \
  83     ALIGN_UP(x, sizeof(union buflib_data))
  84
  85 #ifdef DEBUG
  86     #include <stdio.h>
  87     #define BDEBUGF DEBUGF
  88 #else
  89     #define BDEBUGF(...) do { } while(0)
  90 #endif
  91
  92 static union buflib_data* find_first_free(struct buflib_context *ctx);
  93 static union buflib_data* find_block_before(struct buflib_context *ctx,
  94                                             union buflib_data* block,
  95                                             bool is_free);
  96 /* Initialize buffer manager */
  97 void
  98 buflib_init(struct buflib_context *ctx, void *buf, size_t size)
  99 {
 100     union buflib_data *bd_buf = buf;
 101
 102     /* Align on sizeof(buflib_data), to prevent unaligned access */
 103     ALIGN_BUFFER(bd_buf, size, sizeof(union buflib_data));
 104     size /= sizeof(union buflib_data);
 105     /* The handle table is initialized with no entries */
 106     ctx->handle_table = bd_buf + size;
 107     ctx->last_handle = bd_buf + size;
 108     ctx->first_free_handle = bd_buf + size - 1;
 109     ctx->buf_start = bd_buf;
 110     /* A marker is needed for the end of allocated data, to make sure that it
 111      * does not collide with the handle table, and to detect end-of-buffer.
 112      */
 113     ctx->alloc_end = bd_buf;
 114     ctx->compact = true;
 115
 116     BDEBUGF("buflib initialized with %d.%2d kiB", size / 1024, (size%1000)/10);
 117 }
 118
 119 /* Allocate a new handle, returning 0 on failure */
 120 static inline
 121 union buflib_data* handle_alloc(struct buflib_context *ctx)
 122 {
 123     union buflib_data *handle;
 124     /* first_free_handle is a lower bound on free handles, work through the
 125      * table from there until a handle containing NULL is found, or the end
 126      * of the table is reached.
 127      */
 128     for (handle = ctx->first_free_handle; handle >= ctx->last_handle; handle--)
 129         if (!handle->alloc)
 130             break;
 131     /* If the search went past the end of the table, it means we need to extend
 132      * the table to get a new handle.
 133      */
 134     if (handle < ctx->last_handle)
 135     {
 136         if (handle >= ctx->alloc_end)
 137             ctx->last_handle--;
 138         else
 139             return NULL;
 140     }
 141     handle->val = -1;
 142     return handle;
 143 }
 144
 145 /* Free one handle, shrinking the handle table if it's the last one */
 146 static inline
 147 void handle_free(struct buflib_context *ctx, union buflib_data *handle)
 148 {
 149     handle->alloc = 0;
 150     /* Update free handle lower bound if this handle has a lower index than the
 151      * old one.
 152      */
 153     if (handle > ctx->first_free_handle)
 154         ctx->first_free_handle = handle;
 155     if (handle == ctx->last_handle)
 156         ctx->last_handle++;
 157     else
 158         ctx->compact = false;
 159 }
 160
 161 /* Get the start block of an allocation */
 162 static union buflib_data* handle_to_block(struct buflib_context* ctx, int handle)
 163 {
 164     union buflib_data* name_field =
 165                 (union buflib_data*)buflib_get_name(ctx, handle);
 166
 167     return name_field - 3;
 168 }
 169
 170 /* Shrink the handle table, returning true if its size was reduced, false if
 171  * not
 172  */
 173 static inline
 174 bool
 175 handle_table_shrink(struct buflib_context *ctx)
 176 {
 177     bool rv;
 178     union buflib_data *handle;
 179     for (handle = ctx->last_handle; !(handle->alloc); handle++);
 180     if (handle > ctx->first_free_handle)
 181         ctx->first_free_handle = handle - 1;
 182     rv = handle != ctx->last_handle;
 183     ctx->last_handle = handle;
 184     return rv;
 185 }
 186
 187
 188 /* If shift is non-zero, it represents the number of places to move
 189  * blocks in memory. Calculate the new address for this block,
 190  * update its entry in the handle table, and then move its contents.
 191  *
 192  * Returns false if moving was unsucessful
 193  * (NULL callback or BUFLIB_CB_CANNOT_MOVE was returned)
 194  */
 195 static bool
 196 move_block(struct buflib_context* ctx, union buflib_data* block, int shift)
 197 {
 198     char* new_start;
 199     union buflib_data *new_block, *tmp = block[1].handle;
 200     struct buflib_callbacks *ops = block[2].ops;
 201     if (ops && !ops->move_callback)
 202         return false;
 203
 204     int handle = ctx->handle_table - tmp;
 205     BDEBUGF("%s(): moving \"%s\"(id=%d) by %d(%d)\n", __func__, block[3].name,
 206             handle, shift, shift*sizeof(union buflib_data));
 207     new_block = block + shift;
 208     new_start = tmp->alloc + shift*sizeof(union buflib_data);
 209
 210     /* disable IRQs to make accessing the buffer from interrupt context safe. */
 211     /* protect the move callback, as a cached global pointer might be updated
 212      * in it. and protect "tmp->alloc = new_start" for buflib_get_data() */
 213     disable_irq();
 214     /* call the callback before moving */
 215     if (ops)
 216     {
 217         if (ops->move_callback(handle, tmp->alloc, new_start)
 218                 == BUFLIB_CB_CANNOT_MOVE)
 219         {
 220             enable_irq();
 221             return false;
 222         }
 223     }
 224
 225     tmp->alloc = new_start; /* update handle table */
 226     memmove(new_block, block, block->val * sizeof(union buflib_data));
 227
 228     enable_irq();
 229     return true;
 230 }
 231
 232 /* Compact allocations and handle table, adjusting handle pointers as needed.
 233  * Return true if any space was freed or consolidated, false otherwise.
 234  */
 235 static bool
 236 buflib_compact(struct buflib_context *ctx)
 237 {
 238     BDEBUGF("%s(): Compacting!\n", __func__);
 239     union buflib_data *block,
 240                       *first_free = find_first_free(ctx);
 241     int shift = 0, len;
 242     /* Store the results of attempting to shrink the handle table */
 243     bool ret = handle_table_shrink(ctx);
 244     for(block = first_free; block < ctx->alloc_end; block += len)
 245     {
 246         len = block->val;
 247         /* This block is free, add its length to the shift value */
 248         if (len < 0)
 249         {
 250             shift += len;
 251             len = -len;
 252             continue;
 253         }
 254         /* attempt to fill any hole */
 255         if (-first_free->val >= block->val)
 256         {
 257             intptr_t size = -first_free->val;
 258             union buflib_data* next_block = block + block->val;
 259             if (move_block(ctx, block, first_free - block))
 260             {
 261                 /* moving was successful. Move alloc_end down if necessary */
 262                 if (ctx->alloc_end == next_block)
 263                     ctx->alloc_end = block;
 264                 /* Mark the block behind the just moved as free
 265                  * be careful to not overwrite an existing block */
 266                 if (size != block->val)
 267                 {
 268                     first_free += block->val;
 269                     first_free->val = block->val - size; /* negative */
 270                 }
 271                 continue;
 272             }
 273         }
 274         /* attempt move the allocation by shift */
 275         if (shift)
 276         {
 277             /* failing to move creates a hole,
 278              * therefore mark this block as not allocated */
 279             union buflib_data* target_block = block + shift;
 280             if (!move_block(ctx, block, shift))
 281             {
 282                 target_block->val = shift; /* this is a hole */
 283                 shift = 0;
 284             }
 285             else
 286             {   /* need to update the next free block, since the above hole
 287                  * handling might make shift 0 before alloc_end is reached */
 288                 union buflib_data* new_free = target_block + target_block->val;
 289                 new_free->val = shift;
 290             }
 291         }
 292     }
 293     /* Move the end-of-allocation mark, and return true if any new space has
 294      * been freed.
 295      */
 296     ctx->alloc_end += shift;
 297     ctx->compact = true;
 298     return ret || shift;
 299 }
 300
 301 /* Compact the buffer by trying both shrinking and moving.
 302  *
 303  * Try to move first. If unsuccesfull, try to shrink. If that was successful
 304  * try to move once more as there might be more room now.
 305  */
 306 static bool
 307 buflib_compact_and_shrink(struct buflib_context *ctx, unsigned shrink_hints)
 308 {
 309     bool result = false;
 310     /* if something compacted before already there will be no further gain */
 311     if (!ctx->compact)
 312         result = buflib_compact(ctx);
 313     if (!result)
 314     {
 315         union buflib_data* this;
 316         for(this = ctx->buf_start; this < ctx->alloc_end; this += abs(this->val))
 317         {
 318             if (this->val > 0 && this[2].ops
 319                               && this[2].ops->shrink_callback)
 320             {
 321                 int ret;
 322                 int handle = ctx->handle_table - this[1].handle;
 323                 char* data = this[1].handle->alloc;
 324                 bool last = (this+this->val) == ctx->alloc_end;
 325                 ret = this[2].ops->shrink_callback(handle, shrink_hints,
 326                                             data, (char*)(this+this->val)-data);
 327                 result |= (ret == BUFLIB_CB_OK);
 328                 /* this might have changed in the callback (if
 329                  * it shrinked from the top), get it again */
 330                 this = handle_to_block(ctx, handle);
 331                 /* could also change with shrinking from back */
 332                 if (last)
 333                     ctx->alloc_end = this + this->val;
 334             }
 335         }
 336         /* shrinking was successful at least once, try compaction again */
 337         if (result)
 338             result |= buflib_compact(ctx);
 339     }
 340
 341     return result;
 342 }
 343
 344 /* Shift buffered items by size units, and update handle pointers. The shift
 345  * value must be determined to be safe *before* calling.
 346  */
 347 static void
 348 buflib_buffer_shift(struct buflib_context *ctx, int shift)
 349 {
 350     memmove(ctx->buf_start + shift, ctx->buf_start,
 351         (ctx->alloc_end - ctx->buf_start) * sizeof(union buflib_data));
 352     union buflib_data *handle;
 353     for (handle = ctx->last_handle; handle < ctx->handle_table; handle++)
 354         if (handle->alloc)
 355             handle->alloc += shift;
 356     ctx->buf_start += shift;
 357     ctx->alloc_end += shift;
 358 }
 359
 360 /* Shift buffered items up by size bytes, or as many as possible if size == 0.
 361  * Set size to the number of bytes freed.
 362  */
 363 void*
 364 buflib_buffer_out(struct buflib_context *ctx, size_t *size)
 365 {
 366     if (!ctx->compact)
 367         buflib_compact(ctx);
 368     size_t avail = ctx->last_handle - ctx->alloc_end;
 369     size_t avail_b = avail * sizeof(union buflib_data);
 370     if (*size && *size < avail_b)
 371     {
 372         avail = (*size + sizeof(union buflib_data) - 1)
 373             / sizeof(union buflib_data);
 374         avail_b = avail * sizeof(union buflib_data);
 375     }
 376     *size = avail_b;
 377     void *ret = ctx->buf_start;
 378     buflib_buffer_shift(ctx, avail);
 379     return ret;
 380 }
 381
 382 /* Shift buffered items down by size bytes */
 383 void
 384 buflib_buffer_in(struct buflib_context *ctx, int size)
 385 {
 386     size /= sizeof(union buflib_data);
 387     buflib_buffer_shift(ctx, -size);
 388 }
 389
 390 /* Allocate a buffer of size bytes, returning a handle for it */
 391 int
 392 buflib_alloc(struct buflib_context *ctx, size_t size)
 393 {
 394     return buflib_alloc_ex(ctx, size, "<anonymous>", NULL);
 395 }
 396
 397 /* Allocate a buffer of size bytes, returning a handle for it.
 398  *
 399  * The additional name parameter gives the allocation a human-readable name,
 400  * the ops parameter points to caller-implemented callbacks for moving and
 401  * shrinking. NULL for default callbacks (which do nothing but don't
 402  * prevent moving or shrinking)
 403  */
 404
 405 int
 406 buflib_alloc_ex(struct buflib_context *ctx, size_t size, const char *name,
 407                 struct buflib_callbacks *ops)
 408 {
 409     union buflib_data *handle, *block;
 410     size_t name_len = name ? B_ALIGN_UP(strlen(name)+1) : 0;
 411     bool last;
 412     /* This really is assigned a value before use */
 413     int block_len;
 414     size += name_len;
 415     size = (size + sizeof(union buflib_data) - 1) /
 416            sizeof(union buflib_data)
 417            /* add 4 objects for alloc len, pointer to handle table entry and
 418             * name length, and the ops pointer */
 419            + 4;
 420 handle_alloc:
 421     handle = handle_alloc(ctx);
 422     if (!handle)
 423     {
 424         /* If allocation has failed, and compaction has succeded, it may be
 425          * possible to get a handle by trying again.
 426          */
 427         union buflib_data* last_block = find_block_before(ctx,
 428                                             ctx->alloc_end, false);
 429         struct buflib_callbacks* ops = last_block[2].ops;
 430         unsigned hints = 0;
 431         if (!ops || !ops->shrink_callback)
 432         {   /* the last one isn't shrinkable
 433              * make room in front of a shrinkable and move this alloc */
 434             hints = BUFLIB_SHRINK_POS_FRONT;
 435             hints |= last_block->val * sizeof(union buflib_data);
 436         }
 437         else if (ops && ops->shrink_callback)
 438         {   /* the last is shrinkable, make room for handles directly */
 439             hints = BUFLIB_SHRINK_POS_BACK;
 440             hints |= 16*sizeof(union buflib_data);
 441         }
 442         /* buflib_compact_and_shrink() will compact and move last_block()
 443          * if possible */
 444         if (buflib_compact_and_shrink(ctx, hints))
 445             goto handle_alloc;
 446         return -1;
 447     }
 448
 449 buffer_alloc:
 450     /* need to re-evaluate last before the loop because the last allocation
 451      * possibly made room in its front to fit this, so last would be wrong */
 452     last = false;
 453     for (block = find_first_free(ctx);;block += block_len)
 454     {
 455         /* If the last used block extends all the way to the handle table, the
 456          * block "after" it doesn't have a header. Because of this, it's easier
 457          * to always find the end of allocation by saving a pointer, and always
 458          * calculate the free space at the end by comparing it to the
 459          * last_handle pointer.
 460          */
 461         if(block == ctx->alloc_end)
 462         {
 463             last = true;
 464             block_len = ctx->last_handle - block;
 465             if ((size_t)block_len < size)
 466                 block = NULL;
 467             break;
 468         }
 469         block_len = block->val;
 470         /* blocks with positive length are already allocated. */
 471         if(block_len > 0)
 472             continue;
 473         block_len = -block_len;
 474         /* The search is first-fit, any fragmentation this causes will be
 475          * handled at compaction.
 476          */
 477         if ((size_t)block_len >= size)
 478             break;
 479     }
 480     if (!block)
 481     {
 482         /* Try compacting if allocation failed */
 483         unsigned hint = BUFLIB_SHRINK_POS_FRONT |
 484                     ((size*sizeof(union buflib_data))&BUFLIB_SHRINK_SIZE_MASK);
 485         if (buflib_compact_and_shrink(ctx, hint))
 486         {
 487             goto buffer_alloc;
 488         } else {
 489             handle->val=1;
 490             handle_free(ctx, handle);
 491             return -2;
 492         }
 493     }
 494
 495     /* Set up the allocated block, by marking the size allocated, and storing
 496      * a pointer to the handle.
 497      */
 498     union buflib_data *name_len_slot;
 499     block->val = size;
 500     block[1].handle = handle;
 501     block[2].ops = ops;
 502     strcpy(block[3].name, name);
 503     name_len_slot = (union buflib_data*)B_ALIGN_UP(block[3].name + name_len);
 504     name_len_slot->val = 1 + name_len/sizeof(union buflib_data);
 505     handle->alloc = (char*)(name_len_slot + 1);
 506
 507     block += size;
 508     /* alloc_end must be kept current if we're taking the last block. */
 509     if (last)
 510         ctx->alloc_end = block;
 511     /* Only free blocks *before* alloc_end have tagged length. */
 512     else if ((size_t)block_len > size)
 513         block->val = size - block_len;
 514     /* Return the handle index as a positive integer. */
 515     return ctx->handle_table - handle;
 516 }
 517
 518 static union buflib_data*
 519 find_first_free(struct buflib_context *ctx)
 520 {
 521     union buflib_data* ret = ctx->buf_start;
 522     while(ret < ctx->alloc_end)
 523     {
 524         if (ret->val < 0)
 525             break;
 526         ret += ret->val;
 527     }
 528     /* ret is now either a free block or the same as alloc_end, both is fine */
 529     return ret;
 530 }
 531
 532 /* Finds the free block before block, and returns NULL if it's not free */
 533 static union buflib_data*
 534 find_block_before(struct buflib_context *ctx, union buflib_data* block,
 535                   bool is_free)
 536 {
 537     union buflib_data *ret        = ctx->buf_start,
 538                       *next_block = ret;
 539
 540     /* find the block that's before the current one */
 541     while (next_block < block)
 542     {
 543         ret = next_block;
 544         next_block += abs(ret->val);
 545     }
 546
 547     /* If next_block == block, the above loop didn't go anywhere. If it did,
 548      * and the block before this one is empty, that is the wanted one
 549      */
 550     if (next_block == block && ret < block)
 551     {
 552         if (is_free && ret->val >= 0) /* NULL if found block isn't free */
 553             return NULL;
 554         return ret;
 555     }
 556     return NULL;
 557 }
 558
 559 /* Free the buffer associated with handle_num. */
 560 int
 561 buflib_free(struct buflib_context *ctx, int handle_num)
 562 {
 563     union buflib_data *handle = ctx->handle_table - handle_num,
 564                       *freed_block = handle_to_block(ctx, handle_num),
 565                       *block, *next_block;
 566     /* We need to find the block before the current one, to see if it is free
 567      * and can be merged with this one.
 568      */
 569     block = find_block_before(ctx, freed_block, true);
 570     if (block)
 571     {
 572         block->val -= freed_block->val;
 573     }
 574     else
 575     {
 576     /* Otherwise, set block to the newly-freed block, and mark it free, before
 577      * continuing on, since the code below exects block to point to a free
 578      * block which may have free space after it.
 579      */
 580         block = freed_block;
 581         block->val = -block->val;
 582     }
 583     next_block = block - block->val;
 584     /* Check if we are merging with the free space at alloc_end. */
 585     if (next_block == ctx->alloc_end)
 586         ctx->alloc_end = block;
 587     /* Otherwise, the next block might still be a "normal" free block, and the
 588      * mid-allocation free means that the buffer is no longer compact.
 589      */
 590     else {
 591         ctx->compact = false;
 592         if (next_block->val < 0)
 593             block->val += next_block->val;
 594     }
 595     handle_free(ctx, handle);
 596     handle->alloc = NULL;
 597
 598     return 0; /* unconditionally */
 599 }
 600
 601 /* Return the maximum allocatable memory in bytes */
 602 size_t
 603 buflib_available(struct buflib_context* ctx)
 604 {
 605     /* subtract 5 elements for
 606      * val, handle, name_len, ops and the handle table entry*/
 607     ptrdiff_t diff = (ctx->last_handle - ctx->alloc_end - 5);
 608     diff -= 16; /* space for future handles */
 609     diff *= sizeof(union buflib_data); /* make it bytes */
 610     diff -= 16; /* reserve 16 for the name */
 611
 612     if (diff > 0)
 613         return diff;
 614     else
 615         return 0;
 616 }
 617
 618 /*
 619  * Allocate all available (as returned by buflib_available()) memory and return
 620  * a handle to it
 621  *
 622  * This grabs a lock which can only be unlocked by buflib_free() or
 623  * buflib_shrink(), to protect from further allocations (which couldn't be
 624  * serviced anyway).
 625  */
 626 int
 627 buflib_alloc_maximum(struct buflib_context* ctx, const char* name, size_t *size, struct buflib_callbacks *ops)
 628 {
 629     /* limit name to 16 since that's what buflib_available() accounts for it */
 630     char buf[16];
 631
 632     *size = buflib_available(ctx);
 633     if (*size <= 0) /* OOM */
 634         return -1;
 635
 636     strlcpy(buf, name, sizeof(buf));
 637
 638     return buflib_alloc_ex(ctx, *size, buf, ops);
 639 }
 640
 641 /* Shrink the allocation indicated by the handle according to new_start and
 642  * new_size. Grow is not possible, therefore new_start and new_start + new_size
 643  * must be within the original allocation
 644  */
 645 bool
 646 buflib_shrink(struct buflib_context* ctx, int handle, void* new_start, size_t new_size)
 647 {
 648     char* oldstart = buflib_get_data(ctx, handle);
 649     char* newstart = new_start;
 650     char* newend = newstart + new_size;
 651
 652     /* newstart must be higher and new_size not "negative" */
 653     if (newstart < oldstart || newend < newstart)
 654         return false;
 655     union buflib_data *block = handle_to_block(ctx, handle),
 656                       *old_next_block = block + block->val,
 657                 /* newstart isn't necessarily properly aligned but it
 658                  * needn't be since it's only dereferenced by the user code */
 659                       *aligned_newstart = (union buflib_data*)B_ALIGN_DOWN(newstart),
 660                       *aligned_oldstart = (union buflib_data*)B_ALIGN_DOWN(oldstart),
 661                       *new_next_block =   (union buflib_data*)B_ALIGN_UP(newend),
 662                       *new_block, metadata_size;
 663
 664     /* growing is not supported */
 665     if (new_next_block > old_next_block)
 666         return false;
 667
 668     metadata_size.val = aligned_oldstart - block;
 669     /* update val and the handle table entry */
 670     new_block = aligned_newstart - metadata_size.val;
 671     block[0].val = new_next_block - new_block;
 672
 673     block[1].handle->alloc = newstart;
 674     if (block != new_block)
 675     {
 676         /* move metadata over, i.e. pointer to handle table entry and name
 677          * This is actually the point of no return. Data in the allocation is
 678          * being modified, and therefore we must successfully finish the shrink
 679          * operation */
 680         memmove(new_block, block, metadata_size.val*sizeof(metadata_size));
 681         /* mark the old block unallocated */
 682         block->val = block - new_block;
 683         /* find the block before in order to merge with the new free space */
 684         union buflib_data *free_before = find_block_before(ctx, block, true);
 685         if (free_before)
 686             free_before->val += block->val;
 687
 688         /* We didn't handle size changes yet, assign block to the new one
 689          * the code below the wants block whether it changed or not */
 690         block = new_block;
 691     }
 692
 693     /* Now deal with size changes that create free blocks after the allocation */
 694     if (old_next_block != new_next_block)
 695     {
 696         if (ctx->alloc_end == old_next_block)
 697             ctx->alloc_end = new_next_block;
 698         else if (old_next_block->val < 0)
 699         {   /* enlarge next block by moving it up */
 700             new_next_block->val = old_next_block->val - (old_next_block - new_next_block);
 701         }
 702         else if (old_next_block != new_next_block)
 703         {   /* creating a hole */
 704             /* must be negative to indicate being unallocated */
 705             new_next_block->val = new_next_block - old_next_block;
 706         }
 707     }
 708
 709     return true;
 710 }
 711
 712 const char* buflib_get_name(struct buflib_context *ctx, int handle)
 713 {
 714     union buflib_data *data = ALIGN_DOWN(buflib_get_data(ctx, handle), sizeof (*data));
 715     size_t len = data[-1].val;
 716     if (len <= 1)
 717         return NULL;
 718     return data[-len].name;
 719 }
 720
 721 #ifdef BUFLIB_DEBUG_BLOCKS
 722 void buflib_print_allocs(struct buflib_context *ctx,
 723                                         void (*print)(int, const char*))
 724 {
 725     union buflib_data *this, *end = ctx->handle_table;
 726     char buf[128];
 727     for(this = end - 1; this >= ctx->last_handle; this--)
 728     {
 729         if (!this->alloc) continue;
 730
 731         int handle_num;
 732         const char *name;
 733         union buflib_data *block_start, *alloc_start;
 734         intptr_t alloc_len;
 735
 736         handle_num = end - this;
 737         alloc_start = buflib_get_data(ctx, handle_num);
 738         name = buflib_get_name(ctx, handle_num);
 739         block_start = (union buflib_data*)name - 3;
 740         alloc_len = block_start->val * sizeof(union buflib_data);
 741
 742         snprintf(buf, sizeof(buf),
 743                 "%s(%d):\t%p\n"
 744                 "   \t%p\n"
 745                 "   \t%ld\n",
 746                 name?:"(null)", handle_num, block_start, alloc_start, alloc_len);
 747         /* handle_num is 1-based */
 748         print(handle_num - 1, buf);
 749     }
 750 }
 751
 752 void buflib_print_blocks(struct buflib_context *ctx,
 753                                         void (*print)(int, const char*))
 754 {
 755     char buf[128];
 756     int i = 0;
 757     for(union buflib_data* this = ctx->buf_start;
 758                            this < ctx->alloc_end;
 759                            this += abs(this->val))
 760     {
 761         snprintf(buf, sizeof(buf), "%8p: val: %4ld (%s)",
 762                                 this, this->val,
 763                                 this->val > 0? this[3].name:"<unallocated>");
 764         print(i++, buf);
 765     }
 766 }
 767 #endif
 768
 769 #ifdef BUFLIB_DEBUG_BLOCK_SINGLE
 770 int buflib_get_num_blocks(struct buflib_context *ctx)
 771 {
 772     int i = 0;
 773     for(union buflib_data* this = ctx->buf_start;
 774                            this < ctx->alloc_end;
 775                            this += abs(this->val))
 776     {
 777         i++;
 778     }
 779     return i;
 780 }
 781
 782 void buflib_print_block_at(struct buflib_context *ctx, int block_num,
 783                                 char* buf, size_t bufsize)
 784 {
 785     union buflib_data* this = ctx->buf_start;
 786     while(block_num > 0 && this < ctx->alloc_end)
 787     {
 788         this += abs(this->val);
 789         block_num -= 1;
 790     }
 791     snprintf(buf, bufsize, "%8p: val: %4ld (%s)",
 792                             this, (long)this->val,
 793                             this->val > 0? this[3].name:"<unallocated>");
 794 }
 795
 796 #endif