-
-// -- Cnode Memory Allocation --
-
-/*
- * We allocate chunks but to minimise fragmentation, we store the
- * chunks in a heap ordered such that the chunk with the least number
- * of free elements is at the top. At the end of each chunk we store
- * a pointer to a header somewhere within the chunk. When all
- * elements in a chunk are in use, the pointer is NULL. Given that
- * chunks will always be aligned to a page, we can compute the element
- * index in the chunk using this equation:
- *
- * y * (uintptr_t)el % PAGE_SIZE / gcd % (PAGE_SIZE / gcd)
- *
- * where gcd is the greatest common divisor of elem_size and
- * PAGE_SIZE, (which we calculate using the Euclidean algorithm) and y
- * also falls out of the Euclidean algorithm -- see
- * hfs_cnode_zone_init below. The proof for this is left as an
- * exercise for the reader. Hint: start with the equation:
- *
- * elem_ndx * elem_size = PAGE_SIZE * elem_pg + elem_addr % PAGE_SIZE
- *
- * Now realise that can be made to look like a Diophantine equation
- * (ax + by = c) which is solvable using the Extended Euclidean
- * algorithm and from there you will arrive at the equation above.
- */
-
-enum {
- CHUNK_HDR_MAGIC = 0x6b6e6863, // chnk
- CNODE_MAGIC = 0x65646f6e63736668, // hfscnode
- ELEMENT_ALIGNMENT = 8,
-
- /*
- * We store the pointer to the header for a chunk 8 bytes in from
- * the end of the chunk.
- */
- CHUNK_TAIL_LEN = 8,
-};
-
-typedef struct chunk_hdr
-{
- void *next_free;
- uint32_t magic; // = CHUNK_HDR_MAGIC
- uint16_t free_count;
- uint16_t heap_ndx;
- struct chunk_hdr **phdr;
-} chunk_hdr_t;
-
-static void hfs_cnode_zone_init(hfsmount_t *hfsmp)
-{
- struct cnode_zone *z = &hfsmp->z;
-
- int elem_size = sizeof(cnode_t);
-
- elem_size = roundup(elem_size, ELEMENT_ALIGNMENT);
-
- z->elem_size = elem_size;
-
- // Figure out chunk_size
- int npages, chunk_size, waste;
-
- for (npages = 1;; ++npages) {
- chunk_size = npages * page_size;
- waste = (chunk_size - CHUNK_TAIL_LEN) % elem_size;
-
- // If waste is less than 1%, that's good enough
- if (waste < chunk_size / 100)
- break;
- }
-
- z->chunk_size = chunk_size;
- z->alloc_count = (chunk_size - CHUNK_TAIL_LEN) / elem_size;
-
- // Compute the GCD of elem_size and page_size using Euclidean algorithm
- int t = 1, last_t = 0, r = z->elem_size, last_r = PAGE_SIZE;
-
- while (r != 0) {
- int q = last_r / r;
- int next_r = last_r - q * r;
- last_r = r;
- r = next_r;
- int next_t = last_t - q * t;
- last_t = t;
- t = next_t;
- }
-
- z->gcd = last_r;
- z->y = last_t;
-
- z->heap_max_count = 128 / sizeof(void *);
- z->heap = hfs_malloc(z->heap_max_count * sizeof(void *));
-
-#if DEBUG
- printf("hfs: cnode size %d, chunk size %d, # per chunk %d, waste %d\n",
- elem_size, chunk_size, z->alloc_count, waste);
-#endif
-}
-
-static void hfs_cnode_zone_free(hfsmount_t *hfsmp)
-{
- // Check that all heap chunks are completely free
- struct cnode_zone *z = &hfsmp->z;
-
- for (int i = 0; i < z->heap_count; ++i) {
-#if DEBUG
- hfs_assert(z->heap[i]->free_count == z->alloc_count);
-#else
- if (z->heap[i]->free_count != z->alloc_count) {
- printf("hfs: cnodes leaked!\n");
- continue;
- }
-#endif
- void *chunk = (void *)((uintptr_t)z->heap[i]->phdr
- - (z->chunk_size - CHUNK_TAIL_LEN));
- hfs_free(chunk, z->chunk_size);
- }
-
- hfs_free(z->heap, z->heap_max_count * sizeof(void *));
-}
-
-static void *zel(struct cnode_zone *z, void *chunk, int i)
-{
- return chunk + i * z->elem_size;
-}
-
-static chunk_hdr_t **zphdr(struct cnode_zone *z, void *chunk)
-{
- return chunk + z->chunk_size - CHUNK_TAIL_LEN;
-}
-
-#if 0
-static void hfs_check_heap(hfsmount_t *hfsmp, void *just_removed)
-{
- struct cnode_zone *z = &hfsmp->z;
-
- for (int i = 0; i < z->heap_count; ++i) {
- hfs_assert(z->heap[i]->magic == CHUNK_HDR_MAGIC);
- hfs_assert(z->heap[i]->free_count > 0
- && z->heap[i]->free_count <= z->alloc_count);
- hfs_assert(z->heap[i]->heap_ndx == i);
- void *max_el = z->heap[i]->phdr;
- void *min_el = (void *)((uintptr_t)z->heap[i]->phdr
- + CHUNK_TAIL_LEN - z->chunk_size);
- int count = 1;
- hfs_assert(z->heap[i] != just_removed);
- void *el = z->heap[i]->next_free;
- size_t bitmap_size = (z->alloc_count + 7) / 8;
- uint8_t bitmap[bitmap_size];
- bzero(bitmap, bitmap_size);
- int ndx = (int)((void *)z->heap[i] - min_el) / z->elem_size;
- bitmap[ndx / 8] |= 0x80 >> ndx % 8;
- while (el) {
- hfs_assert(el != just_removed);
- hfs_assert(el >= min_el
- && el < max_el && (el - min_el) % z->elem_size == 0);
- int n = (int)(el - min_el) / z->elem_size;
- hfs_assert(!(bitmap[n / 8] & (0x80 >> n % 8)));
- bitmap[n / 8] |= 0x80 >> n % 8;
- el = *(void **)el;
- ++count;
- }
- hfs_assert(count == z->heap[i]->free_count);
- if (i)
- hfs_assert(z->heap[(i + 1) / 2 - 1]->free_count <= z->heap[i]->free_count);
- }
-}
-#else
-#define hfs_check_heap(a, b) (void)0
-#endif
-
-static void hfs_cnode_set_magic(cnode_t *cp, uint64_t v)
-{
-#if HFS_MALLOC_DEBUG
- cp->magic = v;
-#endif
-}
-
-static cnode_t *hfs_cnode_alloc(hfsmount_t *hfsmp, bool *unlocked)
-{
- hfs_check_heap(hfsmp, NULL);
-
- *unlocked = false;
-
- struct cnode_zone *z = &hfsmp->z;
- void *el;
-
- while (!z->heap_count) {
- if (z->spare) {
- /*
- * We have a spare chunk we can use so initialise it, add
- * it to the heap and return one element from it.
- */
- chunk_hdr_t *chunk_hdr = z->spare;
- z->spare = NULL;
- void *last = NULL;
- for (int i = z->alloc_count - 2; i > 0; --i) {
- void *p = zel(z, chunk_hdr, i);
- *(void **)p = last;
- hfs_cnode_set_magic(p, 0);
- last = p;
- }
- hfs_cnode_set_magic((void *)chunk_hdr, 0);
- chunk_hdr->phdr = zphdr(z, chunk_hdr);
- chunk_hdr->next_free = last;
- chunk_hdr->free_count = z->alloc_count - 1;
- chunk_hdr->heap_ndx = 0;
- // Set the tail to the index of the chunk_hdr
- *zphdr(z, chunk_hdr) = chunk_hdr;
- z->heap[0] = chunk_hdr;
- z->heap_count = 1;
- el = zel(z, chunk_hdr, z->alloc_count - 1);
- hfs_cnode_set_magic(el, 0);
- goto exit;
- }
-
- *unlocked = true;
-
- if (z->allocating) {
- z->waiting = true;
- msleep(z, &hfsmp->hfs_chash_mutex, PINOD | PSPIN,
- "hfs_cnode_alloc", NULL);
- } else {
- z->allocating = true;
- lck_mtx_unlock(&hfsmp->hfs_chash_mutex);
- chunk_hdr_t *chunk_hdr = hfs_malloc(z->chunk_size);
- chunk_hdr->magic = CHUNK_HDR_MAGIC;
- hfs_assert(!((uintptr_t)chunk_hdr & PAGE_MASK));
- lck_mtx_lock_spin(&hfsmp->hfs_chash_mutex);
- z->allocating = false;
- if (z->waiting) {
- wakeup(z);
- z->waiting = false;
- }
- hfs_assert(!z->spare);
- z->spare = chunk_hdr;
- }
- }
-
- chunk_hdr_t *chunk_hdr = z->heap[0];
- if (chunk_hdr->next_free) {
- /*
- * Not the last element in this chunk, so just pull an element
- * off and return it. This chunk should remain at the top of
- * the heap.
- */
- el = chunk_hdr->next_free;
- chunk_hdr->next_free = *(void **)chunk_hdr->next_free;
- --chunk_hdr->free_count;
-
- goto exit;
- }
-
- /*
- * This is the last element in the chunk so we need to fix up the
- * heap.
- */
- el = chunk_hdr;
-
- *chunk_hdr->phdr = NULL;
- chunk_hdr->magic = ~CHUNK_HDR_MAGIC;
-
- if (!--z->heap_count)
- goto exit;
-
- chunk_hdr_t *v = z->heap[z->heap_count];
-
- // Fix heap downwards; offset by one to make easier
- int k = 1;
- chunk_hdr_t **a = &z->heap[0] - 1;
- int N = z->heap_count;
-
- for (;;) {
- // Look at the next level down
- int j = k * 2;
- if (j > N)
- break;
- // Pick the smaller of the two that we're looking at
- if (j < N && a[j]->free_count > a[j+1]->free_count)
- ++j;
- if (v->free_count <= a[j]->free_count)
- break;
- // Shift element at j to k
- a[k] = a[j];
- a[k]->heap_ndx = k - 1;
-
- // Descend
- k = j;
- }
-
- a[k] = v;
- a[k]->heap_ndx = k - 1;
-
-exit:
-
- hfs_check_heap(hfsmp, el);
-
-#if HFS_MALLOC_DEBUG
- if (((cnode_t *)el)->magic == CNODE_MAGIC) {
-#if __x86_64__
- asm("int $3\n");
-#elif __arm64__
- asm("svc 0\n");
-#else
- asm("trap\n");
-#endif
- }
-#endif // HFS_MALLOC_DEBUG
-
- hfs_cnode_set_magic(el, CNODE_MAGIC);
-
- return el;
-}
-
-void hfs_cnode_free(hfsmount_t *hfsmp, cnode_t *cp)
-{
- void *el = cp;
- void *old_heap = NULL;
- size_t old_heap_size = 0;
- struct cnode_zone *z = &hfsmp->z;
-
- int ndx_in_chunk = (z->y * (uintptr_t)el % PAGE_SIZE
- / z->gcd % (PAGE_SIZE / z->gcd));
-
- void *free_chunk = NULL, *chunk = el - ndx_in_chunk * z->elem_size;
-
- lck_mtx_lock_spin(&hfsmp->hfs_chash_mutex);
-
-#if HFS_MALLOC_DEBUG
- hfs_assert(cp->magic == CNODE_MAGIC);
- cp->magic = ~CNODE_MAGIC;
-#endif
-
-loop:
-
- hfs_check_heap(hfsmp, NULL);
-
- chunk_hdr_t *hdr = *zphdr(z, chunk);
-
- int k, orig_k;
-
- if (hdr) {
- /*
- * This chunk already has some free elements in it so we chain this
- * element on and then fix up the heap.
- */
- hfs_assert(hdr->magic == CHUNK_HDR_MAGIC);
-
- *(void **)el = hdr->next_free;
- hdr->next_free = el;
- hfs_assert(hdr->next_free != hdr);
-
- chunk_hdr_t *v;
- orig_k = k = hdr->heap_ndx + 1;
-
- chunk_hdr_t **a = &z->heap[0] - 1;
-
- if (++hdr->free_count == z->alloc_count) {
- // Chunk is totally free
-
- // Always keep at least one chunk on the heap
- if (z->heap_count == 1)
- goto exit;
-
- // Remove the chunk
- free_chunk = chunk;
- --z->heap_count;
- v = z->heap[z->heap_count];
-
- if (k > 1 && a[k / 2]->free_count > v->free_count) {
- do {
- a[k] = a[k / 2];
- a[k]->heap_ndx = k - 1;
- k = k / 2;
- } while (k > 1 && a[k / 2]->free_count > v->free_count);
- a[k] = v;
- a[k]->heap_ndx = k - 1;
- goto exit;
- }
- } else
- v = hdr;
-
- // Fix up the heap
- int N = z->heap_count;
-
- for (;;) {
- // Look at the next level down
- int j = k * 2;
- if (j > N)
- break;
- // Pick the smaller of the two that we're looking at
- if (j < N && a[j]->free_count > a[j+1]->free_count)
- ++j;
- if (v->free_count <= a[j]->free_count)
- break;
- // Shift element at j to k
- a[k] = a[j];
- a[k]->heap_ndx = k - 1;
-
- // Descend
- k = j;
- }
-
- a[k] = v;
- a[k]->heap_ndx = k - 1;
- } else {
- // This element is the first that's free in this chunk
-
- if (z->heap_count == z->heap_max_count) {
- // We need to resize the heap
- int new_max_count = z->heap_max_count * 2;
- lck_mtx_unlock(&hfsmp->hfs_chash_mutex);
- if (old_heap)
- hfs_free(old_heap, old_heap_size);
- struct chunk_hdr **new_heap = hfs_malloc(new_max_count * sizeof(void *));
- lck_mtx_lock_spin(&hfsmp->hfs_chash_mutex);
- // Check to see if someone beat us to it
- if (new_max_count > z->heap_max_count) {
- memcpy(new_heap, z->heap, z->heap_count * sizeof(void *));
- old_heap_size = z->heap_max_count * sizeof(void *);
- z->heap_max_count = new_max_count;
- old_heap = z->heap;
- z->heap = new_heap;
- } else {
- old_heap = new_heap;
- old_heap_size = new_max_count * sizeof(void *);
- }
- // Lock was dropped so we have to go around again
- goto loop;
- }
-
- hdr = (chunk_hdr_t *)el;
- *zphdr(z, chunk) = hdr;
- hdr->free_count = 1;
- hdr->next_free = NULL;
- hdr->heap_ndx = 0;
- hdr->phdr = zphdr(z, chunk);
- hdr->magic = CHUNK_HDR_MAGIC;
-
- // Fix heap upwards; offset by one to make easier
- chunk_hdr_t **a = &z->heap[0] - 1;
-
- if (z->heap_count++) {
- k = z->heap_count;
- chunk_hdr_t *v = z->heap[0];
- while (k > 3 && a[k / 2]->free_count > v->free_count) {
- a[k] = a[k / 2];
- a[k]->heap_ndx = k - 1;
- k = k / 2;
- }
- a[k] = v;
- a[k]->heap_ndx = k - 1;
- }
-
- z->heap[0] = hdr;
- }
-
-exit:
-
- hfs_check_heap(hfsmp, NULL);
- lck_mtx_unlock(&hfsmp->hfs_chash_mutex);
-
- if (old_heap)
- hfs_free(old_heap, old_heap_size);
- if (free_chunk)
- hfs_free(free_chunk, z->chunk_size);
-}