nanocoat/tests/testAllocFreeMerge.c

   1 /* -*- Mode: C; indent-tabs-mode: t; tab-width: 4 -*-
   2 // ---------------------------------------------------------------------------
   3 // SquirrelJME
   4 //     Copyright (C) Stephanie Gawroriski <xer@multiphasicapps.net>
   5 // ---------------------------------------------------------------------------
   6 // SquirrelJME is under the Mozilla Public License Version 2.0.
   7 // See license.mkd for licensing and copyright information.
   8 // -------------------------------------------------------------------------*/
   9
  10 #include "proto.h"
  11 #include "sjme/alloc.h"
  12 #include "test.h"
  13 #include "unit.h"
  14
  15 /** The number of links to allocate. */
  16 #define NUM_LINKS 3
  17
  18 /** The number of which sequences. */
  19 #define NUM_WHICH (NUM_LINKS + 3)
  20
  21 /** Identifier for the front link. */
  22 #define FRONT (NUM_LINKS + 1)
  23
  24 /** Identifier for the back link. */
  25 #define BACK (NUM_LINKS + 2)
  26
  27 /** Identifier of the end of link list. */
  28 #define END NUM_LINKS
  29
  30 /** Free bit. */
  31 #define FREE 64
  32
  33 /** The mask for removing free. */
  34 #define FREE_MASK 63
  35
  36 /** The scenarios available. */
  37 typedef enum testScenarioId
  38 {
  39         /** Left to right. */
  40         sjme_attrUnusedEnum(SCENARIO_LMR),
  41
  42         /** Left, Right, then middle. */
  43         sjme_attrUnusedEnum(SCENARIO_LRM),
  44
  45         /** Middle, then left to right. */
  46         sjme_attrUnusedEnum(SCENARIO_MLR),
  47
  48         /** Middle, then right to left. */
  49         sjme_attrUnusedEnum(SCENARIO_MRL),
  50
  51         /** Right to left. */
  52         sjme_attrUnusedEnum(SCENARIO_RML),
  53
  54         /** Right, left, then middle. */
  55         sjme_attrUnusedEnum(SCENARIO_RLM),
  56
  57         /** The number of scenarios. */
  58         NUM_SCENARIO
  59 } testScenarioId;
  60
  61 /** The sequence of links. */
  62 typedef struct testSequenceType
  63 {
  64         /** The number of used links. */
  65         sjme_jint numUsed;
  66
  67         /** The number of free links. */
  68         sjme_jint numFree;
  69
  70         /** Which links are on the entire chain? */
  71         sjme_jint which[NUM_WHICH];
  72 } testSequenceType;
  73
  74 /** The order of the links. */
  75 typedef struct testOrderType
  76 {
  77         /** The order used. */
  78         sjme_jint order[NUM_LINKS];
  79
  80         /** How many there should be after being freed. */
  81         testSequenceType sequence[NUM_LINKS];
  82 } testOrderType;
  83
  84 /** The actual order to use. */
  85 const testOrderType testLinkOrder[NUM_SCENARIO] =
  86 {
  87         {
  88                 {0, 1, 2},
  89                 {
  90                         {2, 1,
  91                                 {FRONT, 0 | FREE, 1, 2, BACK,
  92                                         END}},
  93                         {1, 1,
  94                                 {FRONT, 0 | FREE, 2, BACK,
  95                                         END}},
  96                         {0, 1,
  97                                 {FRONT, 0 | FREE, BACK,
  98                                         END}}
  99                 }
 100         },
 101         {
 102                 {0, 2, 1},
 103                 {
 104                         {2, 1,
 105                                 {FRONT, 0 | FREE, 1, 2, BACK,
 106                                         END}},
 107                         {1, 2,
 108                                 {FRONT, 0 | FREE, 1, 2 | FREE, BACK,
 109                                         END}},
 110                         {0, 1,
 111                                 {FRONT, 0 | FREE, BACK,
 112                                         END}}
 113                 }
 114         },
 115         {
 116                 {1, 0, 2},
 117                 {
 118                         {2, 1,
 119                                 {FRONT, 0, 1 | FREE, 2, BACK,
 120                                         END}},
 121                         {1, 1,
 122                                 {FRONT, 0 | FREE, 2, BACK,
 123                                         END}},
 124                         {0, 1,
 125                                 {FRONT, 0 | FREE, BACK,
 126                                         END}}
 127                 }
 128         },
 129         {
 130                 {1, 2, 0},
 131                 {
 132                         {2, 1,
 133                                 {FRONT, 0, 1 | FREE, 2, BACK,
 134                                         END}},
 135                         {1, 1,
 136                                 {FRONT, 0, 1 | FREE, BACK,
 137                                         END}},
 138                         {0, 1,
 139                                 {FRONT, 0 | FREE, BACK,
 140                                         END}}
 141                 }
 142         },
 143         {
 144                 {2, 1, 0},
 145                 {
 146                         {2, 1,
 147                                 {FRONT, 0, 1, 2 | FREE, BACK,
 148                                         END}},
 149                         {1, 1,
 150                                 {FRONT, 0, 1 | FREE, BACK,
 151                                         END}},
 152                         {0, 1,
 153                                 {FRONT, 0 | FREE, BACK,
 154                                         END}}
 155                 }
 156         },
 157         {
 158                 {2, 0, 1},
 159                 {
 160                         {2, 1,
 161                                 {FRONT, 0, 1, 2 | FREE, BACK,
 162                                         END}},
 163                         {1, 2,
 164                                 {FRONT, 0 | FREE, 1, 2 | FREE, BACK,
 165                                         END}},
 166                         {0, 1,
 167                                 {FRONT, 0 | FREE, BACK,
 168                                         END}}
 169                 }
 170         }
 171 };
 172
 173 /**
 174  * Tests merging of allocation blocks when freeing them accordingly.
 175  *
 176  * @since 2023/11/25
 177  */
 178 SJME_TEST_DECLARE(testAllocFreeMerge)
 179 {
 180         void* chunk;
 181         sjme_jboolean isLast, isFree, wantFree;
 182         sjme_jint chunkLen, linkNum, scenario, numUsed, numFree, x, atId;
 183         uint8_t* block;
 184         sjme_alloc_link* link;
 185         sjme_alloc_pool* pool;
 186         sjme_alloc_link* rover;
 187         sjme_alloc_link* at;
 188         void* blocks[NUM_LINKS];
 189         sjme_alloc_link* links[NUM_WHICH];
 190         const testOrderType* order;
 191         const testSequenceType* sequence;
 192
 193         /* Allocate data on the stack so it gets cleared. */
 194         chunkLen = 32768;
 195         chunk = sjme_alloca(chunkLen);
 196         if (chunk == NULL)
 197                 return sjme_unit_skip(test, "Could not alloca(%d).",
 198                         (int)chunkLen);
 199
 200         /* Use multiple scenarios regarding the order of blocks to free. */
 201         for (scenario = 0; scenario < NUM_SCENARIO; scenario++)
 202         {
 203                 /* Get the order data. */
 204                 order = &testLinkOrder[scenario];
 205
 206                 /* Initialize the pool. */
 207                 pool = NULL;
 208                 if (sjme_error_is(sjme_alloc_poolInitStatic(&pool,
 209                         chunk, chunkLen)) || pool == NULL)
 210                         return sjme_unit_fail(test, "Could not initialize static pool?");
 211
 212                 /* Allocate each of the links. */
 213                 for (linkNum = 0; linkNum < NUM_LINKS; linkNum++)
 214                 {
 215                         /* Is this the last link? */
 216                         isLast = linkNum >= (NUM_LINKS - 1);
 217
 218                         /* Debug. */
 219                         sjme_message("Link %d of %d (last? %d)",
 220                                 (linkNum + 1), NUM_LINKS, isLast);
 221
 222                         /* Allocate block. */
 223                         blocks[linkNum] = NULL;
 224                         if (sjme_error_is(sjme_alloc(pool,
 225                                 pool->space[SJME_ALLOC_POOL_SPACE_FREE].usable /
 226                                         (isLast ? 1 : 2),
 227                                 &blocks[linkNum])) || blocks[linkNum] == NULL)
 228                                 return sjme_unit_fail(test, "Could not allocate link?");
 229
 230                         /* Get the link. */
 231                         links[linkNum] = NULL;
 232                         if (sjme_error_is(sjme_alloc_getLink(blocks[linkNum],
 233                                 &links[linkNum])) || links[linkNum] == NULL)
 234                                 return sjme_unit_fail(test, "Could not get link?");
 235
 236                         /* The last block should claim all the free space. */
 237                         if (isLast)
 238                                 sjme_unit_equalI(test,
 239                                         0, pool->space[SJME_ALLOC_POOL_SPACE_FREE].usable,
 240                                         "All of the free space was not taken?");
 241                 }
 242
 243                 /* Seed front and back links which are constant. */
 244                 links[FRONT] = pool->frontLink;
 245                 links[BACK] = pool->backLink;
 246
 247                 /* Free the links in the specified order and test the result. */
 248                 for (linkNum = 0; linkNum < NUM_LINKS; linkNum++)
 249                 {
 250                         /* Get the sequence from the order. */
 251                         sequence = &order->sequence[linkNum];
 252
 253                         /* Which link is this? */
 254                         block = blocks[order->order[linkNum]];
 255                         link = links[order->order[linkNum]];
 256
 257                         /* Free the link. */
 258                         if (sjme_error_is(sjme_alloc_free(block)))
 259                                 return sjme_unit_fail(test, "Could not free link.");
 260
 261                         /* Go through the entire chain. */
 262                         numUsed = numFree = 0;
 263                         rover = pool->frontLink;
 264                         for (x = 0; x < NUM_WHICH; x++)
 265                         {
 266                                 /* End of list? Stop. */
 267                                 if (sequence->which[x] == END)
 268                                         break;
 269
 270                                 /* Get the link this is. */
 271                                 atId = x & FREE_MASK;
 272                                 at = links[sequence->which[atId]];
 273
 274                                 /* Must be this one. */
 275                                 sjme_unit_equalP(test, rover, at,
 276                                         "Incorrect sequence %d.%d.%d?", scenario, linkNum, x);
 277
 278                                 /* Is the block free or not? */
 279                                 if (atId != FRONT && atId != BACK)
 280                                 {
 281                                         /* Is this block free? */
 282                                         isFree = (rover->space == SJME_ALLOC_POOL_SPACE_FREE);
 283
 284                                         /* The freeness should match. */
 285                                         wantFree = !!(sequence->which[atId] & FREE);
 286                                         sjme_unit_equalI(test,
 287                                                 isFree, wantFree,
 288                                                 "Incorrect freeness %d.%d.%d?", scenario, linkNum, x);
 289
 290                                         /* Count up. */
 291                                         if (isFree)
 292                                                 numFree++;
 293                                         else
 294                                                 numUsed++;
 295                                 }
 296
 297                                 /* Go the next link. */
 298                                 rover = rover->next;
 299                         }
 300
 301                         /* Free and used counts should match. */
 302                         sjme_unit_equalI(test, numFree, sequence->numFree,
 303                                 "Free match incorrect %d.%d?", scenario, linkNum);
 304                         sjme_unit_equalI(test, numUsed, sequence->numUsed,
 305                                 "Free match incorrect %d.%d?", scenario, linkNum);
 306                 }
 307         }
 308
 309         /* Success! */
 310         return SJME_TEST_RESULT_PASS;
 311 }