+static region_t
+small_find_msize_region(szone_t *szone, magazine_t *small_mag_ptr, mag_index_t mag_index, msize_t msize)
+{
+ free_list_t *ptr;
+ grain_t slot = (msize <= szone->num_small_slots) ? msize - 1 : szone->num_small_slots - 1;
+ free_list_t **free_list = small_mag_ptr->mag_free_list;
+ free_list_t **the_slot = free_list + slot;
+ free_list_t **limit;
+ unsigned bitmap;
+
+ // Assumes we've locked the magazine
+ CHECK_MAGAZINE_PTR_LOCKED(szone, small_mag_ptr, __PRETTY_FUNCTION__);
+
+ // Look for an exact match by checking the freelist for this msize.
+ ptr = *the_slot;
+ if (ptr)
+ return SMALL_REGION_FOR_PTR(ptr);
+
+ // Mask off the bits representing slots holding free blocks smaller than
+ // the size we need.
+ if (szone->is_largemem) {
+ // BITMAPN_CTZ implementation
+ unsigned idx = slot >> 5;
+ bitmap = 0;
+ unsigned mask = ~ ((1 << (slot & 31)) - 1);
+ for ( ; idx < SMALL_BITMAP_WORDS; ++idx ) {
+ bitmap = small_mag_ptr->mag_bitmap[idx] & mask;
+ if (bitmap != 0)
+ break;
+ mask = ~0U;
+ }
+ // Check for fallthrough: No bits set in bitmap
+ if ((bitmap == 0) && (idx == SMALL_BITMAP_WORDS))
+ return NULL;
+
+ // Start looking at the first set bit, plus 32 bits for every word of
+ // zeroes or entries that were too small.
+ slot = BITMAP32_CTZ((&bitmap)) + (idx * 32);
+ } else {
+ bitmap = small_mag_ptr->mag_bitmap[0] & ~ ((1 << slot) - 1);
+ if (!bitmap)
+ return NULL;
+
+ slot = BITMAP32_CTZ((&bitmap));
+ }
+ limit = free_list + szone->num_small_slots - 1;
+ free_list += slot;
+
+ if (free_list < limit) {
+ ptr = *free_list;
+ if (ptr)
+ return SMALL_REGION_FOR_PTR(ptr);
+ else {
+ /* Shouldn't happen. Fall through to look at last slot. */
+#if DEBUG_MALLOC
+ malloc_printf("in small_malloc_from_free_list(), mag_bitmap out of sync, slot=%d\n",slot);
+#endif
+ }
+ }
+
+ // We are now looking at the last slot, which contains blocks equal to, or
+ // due to coalescing of free blocks, larger than (num_small_slots - 1) * (small quantum size).
+ ptr = *limit;
+ if (ptr)
+ return SMALL_REGION_FOR_PTR(ptr);
+
+ return NULL;
+}
+
projects / apple / libc.git / commitdiff
