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