tests/zalloc_buddy.c

   1 #include <darwintest.h>
   2 #include <darwintest_utils.h>
   3
   4 #include <mach/mach.h>
   5 #include <sys/mman.h>
   6
   7 #undef __abortlike
   8 #define __abortlike
   9 #define panic(fmt, ...) ({ T_FAIL(fmt, __VA_ARGS__); abort(); })
  10
  11 #define __security_const_late
  12 #define ZALLOC_TEST 1
  13 #include "../osfmk/kern/zalloc.c"
  14
  15 #define ZBA_TEST_SIZE  (1ul << 20)
  16
  17 static void
  18 zba_populate_any(vm_address_t addr, vm_size_t size)
  19 {
  20         int rc = mprotect((void *)addr, size, PROT_READ | PROT_WRITE);
  21         T_QUIET; T_ASSERT_POSIX_SUCCESS(rc, "mprotect");
  22 }
  23
  24 static void
  25 zba_populate_nope(vm_address_t addr, vm_size_t size)
  26 {
  27 #pragma unused(addr, size)
  28         T_FAIL("Trying to extend the storage");
  29         T_END;
  30 }
  31
  32 static void
  33 zba_test_allow_extension(void)
  34 {
  35         zba_test_info.zbats_populate = zba_populate_any;
  36 }
  37
  38 static void
  39 zba_test_disallow_extension(void)
  40 {
  41         zba_test_info.zbats_populate = zba_populate_nope;
  42 }
  43
  44 static void
  45 zba_test_setup(void)
  46 {
  47         kern_return_t kr;
  48         int rc;
  49
  50         kr = vm_allocate(mach_task_self(), &zba_test_info.zbats_base,
  51             ZBA_TEST_SIZE + ZBA_CHUNK_SIZE, VM_FLAGS_ANYWHERE);
  52         T_ASSERT_MACH_SUCCESS(kr, "vm_allocate()");
  53
  54         zba_test_info.zbats_base = roundup(zba_test_info.zbats_base,
  55             ZBA_CHUNK_SIZE);
  56
  57         rc = mprotect(zba_base_header(), ZBA_TEST_SIZE, PROT_NONE);
  58         T_ASSERT_POSIX_SUCCESS(rc, "mprotect");
  59
  60         T_LOG("SETUP allocator with base at %p", zba_base_header());
  61
  62         zba_test_allow_extension();
  63         zba_populate(0);
  64         zba_init_chunk(0);
  65 }
  66
  67 T_DECL(zone_buddy_allocator_encodings, "test the buddy allocator formulas")
  68 {
  69         uint8_t bits[sizeof(zba_base_header()->zbah_bits)] = { };
  70
  71         for (uint32_t o = ZBA_MAX_ORDER + 1; o-- > 0;) {
  72                 for (vm_address_t pos = 0; pos < ZBA_CHUNK_SIZE; pos += ZBA_GRANULE << o) {
  73                         struct zone_bits_chain *zbc;
  74                         size_t node = zba_node(pos, o);
  75
  76                         zbc = zba_chain_for_node(NULL, node, o);
  77                         T_QUIET; T_ASSERT_EQ(pos, (vm_offset_t)zbc,
  78                             "zba_node / zba_chain_for_node is reversible (pos: %lx, node %zd)",
  79                             pos, node);
  80
  81
  82                         if (o == 0) {
  83                                 // leaf nodes aren't represented in the bitmap
  84                                 continue;
  85                         }
  86                         T_QUIET; T_ASSERT_LT(node, 8 * sizeof(bits), "fits in bitfield: %zd", pos);
  87                         T_QUIET; T_ASSERT_EQ(0, bits[node / 8] & (1 << (node % 8)), "never seen");
  88                         bits[node / 8] ^= 1 << (node % 8);
  89                 }
  90         }
  91
  92         T_PASS("zba_node, zba_chain_for_node look sane");
  93 }
  94
  95 T_DECL(zone_buddy_allocator, "test the zone bits setup")
  96 {
  97         vm_address_t base, pos;
  98
  99         zba_test_setup();
 100
 101         zba_test_disallow_extension();
 102
 103         base = (vm_address_t)zba_slot_base();
 104         for (pos = zba_chunk_header_size(0); pos < ZBA_CHUNK_SIZE; pos += ZBA_GRANULE) {
 105                 T_QUIET; T_ASSERT_EQ(base + pos, zba_alloc(0), "alloc");
 106                 *(uint64_t *)(base + pos) = ~0ull;
 107         }
 108         for (pos = zba_chunk_header_size(0); pos < ZBA_CHUNK_SIZE; pos += ZBA_GRANULE) {
 109                 zba_free(base + pos, 0);
 110         }
 111
 112         for (pos = zba_chunk_header_size(0); pos < ZBA_CHUNK_SIZE; pos += ZBA_GRANULE) {
 113                 T_QUIET; T_ASSERT_EQ(base + pos, zba_alloc(0), "alloc");
 114                 *(uint64_t *)(base + pos) = ~0ull;
 115         }
 116         zba_test_allow_extension();
 117
 118         base += ZBA_CHUNK_SIZE;
 119         for (pos = zba_chunk_header_size(1); pos < ZBA_CHUNK_SIZE; pos += ZBA_GRANULE) {
 120                 T_QUIET; T_ASSERT_EQ(base + pos, zba_alloc(0), "alloc");
 121                 *(uint64_t *)(base + pos) = ~0ull;
 122         }
 123
 124         for (pos = zba_chunk_header_size(1); pos < ZBA_CHUNK_SIZE; pos += ZBA_GRANULE) {
 125                 zba_free(base + pos, 0);
 126         }
 127         base -= ZBA_CHUNK_SIZE;
 128         for (pos = zba_chunk_header_size(0); pos < ZBA_CHUNK_SIZE; pos += ZBA_GRANULE) {
 129                 zba_free(base + pos, 0);
 130         }
 131 }