--- /dev/null
+// SPDX-License-Identifier: BSD-3-Clause
+/* Copyright 2016-2020, Intel Corporation */
+
+/*
+ * alloc_class.c -- implementation of allocation classes
+ */
+
+#include <float.h>
+#include <string.h>
+
+#include "alloc_class.h"
+#include "heap_layout.h"
+#include "util.h"
+#include "out.h"
+#include "bucket.h"
+#include "critnib.h"
+
+#define RUN_CLASS_KEY_PACK(map_idx_s, flags_s, size_idx_s)\
+((uint64_t)(map_idx_s) << 32 |\
+(uint64_t)(flags_s) << 16 |\
+(uint64_t)(size_idx_s))
+
+/*
+ * Value used to mark a reserved spot in the bucket array.
+ */
+#define ACLASS_RESERVED ((void *)0xFFFFFFFFULL)
+
+/*
+ * The last size that is handled by runs.
+ */
+#define MAX_RUN_SIZE (CHUNKSIZE * 10)
+
+/*
+ * Maximum number of bytes the allocation class generation algorithm can decide
+ * to waste in a single run chunk.
+ */
+#define MAX_RUN_WASTED_BYTES 1024
+
+/*
+ * Allocation categories are used for allocation classes generation. Each one
+ * defines the biggest handled size (in bytes) and step pct of the generation
+ * process. The step percentage defines maximum allowed external fragmentation
+ * for the category.
+ */
+#define MAX_ALLOC_CATEGORIES 9
+
+/*
+ * The first size (in byes) which is actually used in the allocation
+ * class generation algorithm. All smaller sizes use the first predefined bucket
+ * with the smallest run unit size.
+ */
+#define FIRST_GENERATED_CLASS_SIZE 128
+
+/*
+ * The granularity of the allocation class generation algorithm.
+ */
+#define ALLOC_BLOCK_SIZE_GEN 64
+
+/*
+ * The first predefined allocation class size
+ */
+#define MIN_UNIT_SIZE 128
+
+static const struct {
+ size_t size;
+ float step;
+} categories[MAX_ALLOC_CATEGORIES] = {
+ /* dummy category - the first allocation class is predefined */
+ {FIRST_GENERATED_CLASS_SIZE, 0.05f},
+ {1024, 0.05f},
+ {2048, 0.05f},
+ {4096, 0.05f},
+ {8192, 0.05f},
+ {16384, 0.05f},
+ {32768, 0.05f},
+ {131072, 0.05f},
+ {393216, 0.05f},
+};
+
+#define RUN_UNIT_MAX_ALLOC 8U
+
+/*
+ * Every allocation has to be a multiple of at least 8 because we need to
+ * ensure proper alignment of every pmem structure.
+ */
+#define ALLOC_BLOCK_SIZE 16
+
+/*
+ * Converts size (in bytes) to number of allocation blocks.
+ */
+#define SIZE_TO_CLASS_MAP_INDEX(_s, _g) (1 + (((_s) - 1) / (_g)))
+
+/*
+ * Target number of allocations per run instance.
+ */
+#define RUN_MIN_NALLOCS 200
+
+/*
+ * Hard limit of chunks per single run.
+ */
+#define RUN_SIZE_IDX_CAP (16)
+
+#define ALLOC_CLASS_DEFAULT_FLAGS CHUNK_FLAG_FLEX_BITMAP
+
+struct alloc_class_collection {
+ size_t granularity;
+
+ struct alloc_class *aclasses[MAX_ALLOCATION_CLASSES];
+
+ /*
+ * The last size (in bytes) that is handled by runs, everything bigger
+ * uses the default class.
+ */
+ size_t last_run_max_size;
+
+ /* maps allocation classes to allocation sizes, excluding the header! */
+ uint8_t *class_map_by_alloc_size;
+
+ /* maps allocation classes to run unit sizes */
+ struct critnib *class_map_by_unit_size;
+
+ int fail_on_missing_class;
+ int autogenerate_on_missing_class;
+};
+
+/*
+ * alloc_class_find_first_free_slot -- searches for the
+ * first available allocation class slot
+ *
+ * This function must be thread-safe because allocation classes can be created
+ * at runtime.
+ */
+int
+alloc_class_find_first_free_slot(struct alloc_class_collection *ac,
+ uint8_t *slot)
+{
+ LOG(10, NULL);
+
+ for (int n = 0; n < MAX_ALLOCATION_CLASSES; ++n) {
+ if (util_bool_compare_and_swap64(&ac->aclasses[n],
+ NULL, ACLASS_RESERVED)) {
+ *slot = (uint8_t)n;
+ return 0;
+ }
+ }
+
+ return -1;
+}
+
+/*
+ * alloc_class_reserve -- reserve the specified class id
+ */
+int
+alloc_class_reserve(struct alloc_class_collection *ac, uint8_t id)
+{
+ LOG(10, NULL);
+
+ return util_bool_compare_and_swap64(&ac->aclasses[id],
+ NULL, ACLASS_RESERVED) ? 0 : -1;
+}
+
+/*
+ * alloc_class_reservation_clear -- removes the reservation on class id
+ */
+static void
+alloc_class_reservation_clear(struct alloc_class_collection *ac, int id)
+{
+ LOG(10, NULL);
+
+ int ret = util_bool_compare_and_swap64(&ac->aclasses[id],
+ ACLASS_RESERVED, NULL);
+ ASSERT(ret);
+}
+
+/*
+ * alloc_class_new -- creates a new allocation class
+ */
+struct alloc_class *
+alloc_class_new(int id, struct alloc_class_collection *ac,
+ enum alloc_class_type type, enum header_type htype,
+ size_t unit_size, size_t alignment,
+ uint32_t size_idx)
+{
+ LOG(10, NULL);
+
+ struct alloc_class *c = Malloc(sizeof(*c));
+ if (c == NULL)
+ goto error_class_alloc;
+
+ c->unit_size = unit_size;
+ c->header_type = htype;
+ c->type = type;
+ c->flags = (uint16_t)
+ (header_type_to_flag[c->header_type] |
+ (alignment ? CHUNK_FLAG_ALIGNED : 0)) |
+ ALLOC_CLASS_DEFAULT_FLAGS;
+
+ switch (type) {
+ case CLASS_HUGE:
+ id = DEFAULT_ALLOC_CLASS_ID;
+ break;
+ case CLASS_RUN:
+ c->rdsc.alignment = alignment;
+ memblock_run_bitmap(&size_idx, c->flags, unit_size,
+ alignment, NULL, &c->rdsc.bitmap);
+ c->rdsc.nallocs = c->rdsc.bitmap.nbits;
+ c->rdsc.size_idx = size_idx;
+
+ /* these two fields are duplicated from class */
+ c->rdsc.unit_size = c->unit_size;
+ c->rdsc.flags = c->flags;
+
+ uint8_t slot = (uint8_t)id;
+ if (id < 0 && alloc_class_find_first_free_slot(ac,
+ &slot) != 0)
+ goto error_class_alloc;
+ id = slot;
+
+ size_t map_idx = SIZE_TO_CLASS_MAP_INDEX(c->unit_size,
+ ac->granularity);
+ ASSERT(map_idx <= UINT32_MAX);
+ uint32_t map_idx_s = (uint32_t)map_idx;
+ uint16_t size_idx_s = (uint16_t)size_idx;
+ uint16_t flags_s = (uint16_t)c->flags;
+ uint64_t k = RUN_CLASS_KEY_PACK(map_idx_s,
+ flags_s, size_idx_s);
+ if (critnib_insert(ac->class_map_by_unit_size,
+ k, c) != 0) {
+ ERR("unable to register allocation class");
+ goto error_map_insert;
+ }
+
+ break;
+ default:
+ ASSERT(0);
+ }
+
+ c->id = (uint8_t)id;
+ ac->aclasses[c->id] = c;
+ return c;
+
+error_map_insert:
+ Free(c);
+error_class_alloc:
+ if (id >= 0)
+ alloc_class_reservation_clear(ac, id);
+ return NULL;
+}
+
+/*
+ * alloc_class_delete -- (internal) deletes an allocation class
+ */
+void
+alloc_class_delete(struct alloc_class_collection *ac,
+ struct alloc_class *c)
+{
+ LOG(10, NULL);
+
+ ac->aclasses[c->id] = NULL;
+ Free(c);
+}
+
+/*
+ * alloc_class_find_or_create -- (internal) searches for the
+ * biggest allocation class for which unit_size is evenly divisible by n.
+ * If no such class exists, create one.
+ */
+static struct alloc_class *
+alloc_class_find_or_create(struct alloc_class_collection *ac, size_t n)
+{
+ LOG(10, NULL);
+
+ COMPILE_ERROR_ON(MAX_ALLOCATION_CLASSES > UINT8_MAX);
+ uint64_t required_size_bytes = n * RUN_MIN_NALLOCS;
+ uint32_t required_size_idx = 1;
+ if (required_size_bytes > RUN_DEFAULT_SIZE) {
+ required_size_bytes -= RUN_DEFAULT_SIZE;
+ required_size_idx +=
+ CALC_SIZE_IDX(CHUNKSIZE, required_size_bytes);
+ if (required_size_idx > RUN_SIZE_IDX_CAP)
+ required_size_idx = RUN_SIZE_IDX_CAP;
+ }
+
+ for (int i = MAX_ALLOCATION_CLASSES - 1; i >= 0; --i) {
+ struct alloc_class *c = ac->aclasses[i];
+
+ if (c == NULL || c->type == CLASS_HUGE ||
+ c->rdsc.size_idx < required_size_idx)
+ continue;
+
+ if (n % c->unit_size == 0 &&
+ n / c->unit_size <= RUN_UNIT_MAX_ALLOC)
+ return c;
+ }
+
+ /*
+ * In order to minimize the wasted space at the end of the run the
+ * run data size must be divisible by the allocation class unit size
+ * with the smallest possible remainder, preferably 0.
+ */
+ struct run_bitmap b;
+ size_t runsize_bytes = 0;
+ do {
+ if (runsize_bytes != 0) /* don't increase on first iteration */
+ n += ALLOC_BLOCK_SIZE_GEN;
+
+ uint32_t size_idx = required_size_idx;
+ memblock_run_bitmap(&size_idx, ALLOC_CLASS_DEFAULT_FLAGS, n, 0,
+ NULL, &b);
+
+ runsize_bytes = RUN_CONTENT_SIZE_BYTES(size_idx) - b.size;
+ } while ((runsize_bytes % n) > MAX_RUN_WASTED_BYTES);
+
+ /*
+ * Now that the desired unit size is found the existing classes need
+ * to be searched for possible duplicates. If a class that can handle
+ * the calculated size already exists, simply return that.
+ */
+ for (int i = 1; i < MAX_ALLOCATION_CLASSES; ++i) {
+ struct alloc_class *c = ac->aclasses[i];
+ if (c == NULL || c->type == CLASS_HUGE)
+ continue;
+ if (n / c->unit_size <= RUN_UNIT_MAX_ALLOC &&
+ n % c->unit_size == 0)
+ return c;
+ if (c->unit_size == n)
+ return c;
+ }
+
+ return alloc_class_new(-1, ac, CLASS_RUN, HEADER_COMPACT, n, 0,
+ required_size_idx);
+}
+
+/*
+ * alloc_class_find_min_frag -- searches for an existing allocation
+ * class that will provide the smallest internal fragmentation for the given
+ * size.
+ */
+static struct alloc_class *
+alloc_class_find_min_frag(struct alloc_class_collection *ac, size_t n)
+{
+ LOG(10, NULL);
+
+ struct alloc_class *best_c = NULL;
+ size_t lowest_waste = SIZE_MAX;
+
+ ASSERTne(n, 0);
+
+ /*
+ * Start from the largest buckets in order to minimize unit size of
+ * allocated memory blocks.
+ */
+ for (int i = MAX_ALLOCATION_CLASSES - 1; i >= 0; --i) {
+ struct alloc_class *c = ac->aclasses[i];
+
+ /* can't use alloc classes /w no headers by default */
+ if (c == NULL || c->header_type == HEADER_NONE)
+ continue;
+
+ size_t real_size = n + header_type_to_size[c->header_type];
+
+ size_t units = CALC_SIZE_IDX(c->unit_size, real_size);
+
+ /* can't exceed the maximum allowed run unit max */
+ if (c->type == CLASS_RUN && units > RUN_UNIT_MAX_ALLOC)
+ continue;
+
+ if (c->unit_size * units == real_size)
+ return c;
+
+ size_t waste = (c->unit_size * units) - real_size;
+
+ /*
+ * If we assume that the allocation class is only ever going to
+ * be used with exactly one size, the effective internal
+ * fragmentation would be increased by the leftover
+ * memory at the end of the run.
+ */
+ if (c->type == CLASS_RUN) {
+ size_t wasted_units = c->rdsc.nallocs % units;
+ size_t wasted_bytes = wasted_units * c->unit_size;
+ size_t waste_avg_per_unit = wasted_bytes /
+ c->rdsc.nallocs;
+
+ waste += waste_avg_per_unit;
+ }
+
+ if (best_c == NULL || lowest_waste > waste) {
+ best_c = c;
+ lowest_waste = waste;
+ }
+ }
+
+ ASSERTne(best_c, NULL);
+ return best_c;
+}
+
+/*
+ * alloc_class_collection_new -- creates a new collection of allocation classes
+ */
+struct alloc_class_collection *
+alloc_class_collection_new()
+{
+ LOG(10, NULL);
+
+ struct alloc_class_collection *ac = Zalloc(sizeof(*ac));
+ if (ac == NULL)
+ return NULL;
+
+ ac->granularity = ALLOC_BLOCK_SIZE;
+ ac->last_run_max_size = MAX_RUN_SIZE;
+ ac->fail_on_missing_class = 0;
+ ac->autogenerate_on_missing_class = 1;
+
+ size_t maps_size = (MAX_RUN_SIZE / ac->granularity) + 1;
+
+ if ((ac->class_map_by_alloc_size = Malloc(maps_size)) == NULL)
+ goto error;
+ if ((ac->class_map_by_unit_size = critnib_new()) == NULL)
+ goto error;
+
+ memset(ac->class_map_by_alloc_size, 0xFF, maps_size);
+
+ if (alloc_class_new(-1, ac, CLASS_HUGE, HEADER_COMPACT,
+ CHUNKSIZE, 0, 1) == NULL)
+ goto error;
+
+ struct alloc_class *predefined_class =
+ alloc_class_new(-1, ac, CLASS_RUN, HEADER_COMPACT,
+ MIN_UNIT_SIZE, 0, 1);
+ if (predefined_class == NULL)
+ goto error;
+
+ for (size_t i = 0; i < FIRST_GENERATED_CLASS_SIZE / ac->granularity;
+ ++i) {
+ ac->class_map_by_alloc_size[i] = predefined_class->id;
+ }
+
+ /*
+ * Based on the defined categories, a set of allocation classes is
+ * created. The unit size of those classes is depended on the category
+ * initial size and step.
+ */
+ size_t granularity_mask = ALLOC_BLOCK_SIZE_GEN - 1;
+ for (int c = 1; c < MAX_ALLOC_CATEGORIES; ++c) {
+ size_t n = categories[c - 1].size + ALLOC_BLOCK_SIZE_GEN;
+ do {
+ if (alloc_class_find_or_create(ac, n) == NULL)
+ goto error;
+
+ float stepf = (float)n * categories[c].step;
+ size_t stepi = (size_t)stepf;
+ stepi = (stepf - (float)stepi < FLT_EPSILON) ?
+ stepi : stepi + 1;
+
+ n += (stepi + (granularity_mask)) & ~granularity_mask;
+ } while (n <= categories[c].size);
+ }
+
+ /*
+ * Find the largest alloc class and use it's unit size as run allocation
+ * threshold.
+ */
+ uint8_t largest_aclass_slot;
+ for (largest_aclass_slot = MAX_ALLOCATION_CLASSES - 1;
+ largest_aclass_slot > 0 &&
+ ac->aclasses[largest_aclass_slot] == NULL;
+ --largest_aclass_slot) {
+ /* intentional NOP */
+ }
+
+ struct alloc_class *c = ac->aclasses[largest_aclass_slot];
+
+ /*
+ * The actual run might contain less unit blocks than the theoretical
+ * unit max variable. This may be the case for very large unit sizes.
+ */
+ size_t real_unit_max = c->rdsc.nallocs < RUN_UNIT_MAX_ALLOC ?
+ c->rdsc.nallocs : RUN_UNIT_MAX_ALLOC;
+
+ size_t theoretical_run_max_size = c->unit_size * real_unit_max;
+
+ ac->last_run_max_size = MAX_RUN_SIZE > theoretical_run_max_size ?
+ theoretical_run_max_size : MAX_RUN_SIZE;
+
+#ifdef DEBUG
+ /*
+ * Verify that each bucket's unit size points back to the bucket by the
+ * bucket map. This must be true for the default allocation classes,
+ * otherwise duplicate buckets will be created.
+ */
+ for (size_t i = 0; i < MAX_ALLOCATION_CLASSES; ++i) {
+ struct alloc_class *c = ac->aclasses[i];
+
+ if (c != NULL && c->type == CLASS_RUN) {
+ ASSERTeq(i, c->id);
+ ASSERTeq(alloc_class_by_run(ac, c->unit_size,
+ c->flags, c->rdsc.size_idx), c);
+ }
+ }
+#endif
+
+ return ac;
+
+error:
+ alloc_class_collection_delete(ac);
+
+ return NULL;
+}
+
+/*
+ * alloc_class_collection_delete -- deletes the allocation class collection and
+ * all of the classes within it
+ */
+void
+alloc_class_collection_delete(struct alloc_class_collection *ac)
+{
+ LOG(10, NULL);
+
+ for (size_t i = 0; i < MAX_ALLOCATION_CLASSES; ++i) {
+ struct alloc_class *c = ac->aclasses[i];
+ if (c != NULL) {
+ alloc_class_delete(ac, c);
+ }
+ }
+
+ if (ac->class_map_by_unit_size)
+ critnib_delete(ac->class_map_by_unit_size);
+ Free(ac->class_map_by_alloc_size);
+ Free(ac);
+}
+
+/*
+ * alloc_class_assign_by_size -- (internal) chooses the allocation class that
+ * best approximates the provided size
+ */
+static struct alloc_class *
+alloc_class_assign_by_size(struct alloc_class_collection *ac,
+ size_t size)
+{
+ LOG(10, NULL);
+
+ size_t class_map_index = SIZE_TO_CLASS_MAP_INDEX(size,
+ ac->granularity);
+
+ struct alloc_class *c = alloc_class_find_min_frag(ac,
+ class_map_index * ac->granularity);
+ ASSERTne(c, NULL);
+
+ /*
+ * We don't lock this array because locking this section here and then
+ * bailing out if someone else was faster would be still slower than
+ * just calculating the class and failing to assign the variable.
+ * We are using a compare and swap so that helgrind/drd don't complain.
+ */
+ util_bool_compare_and_swap64(
+ &ac->class_map_by_alloc_size[class_map_index],
+ MAX_ALLOCATION_CLASSES, c->id);
+
+ return c;
+}
+
+/*
+ * alloc_class_by_alloc_size -- returns allocation class that is assigned
+ * to handle an allocation of the provided size
+ */
+struct alloc_class *
+alloc_class_by_alloc_size(struct alloc_class_collection *ac, size_t size)
+{
+ if (size < ac->last_run_max_size) {
+ uint8_t class_id = ac->class_map_by_alloc_size[
+ SIZE_TO_CLASS_MAP_INDEX(size, ac->granularity)];
+
+ if (class_id == MAX_ALLOCATION_CLASSES) {
+ if (ac->fail_on_missing_class)
+ return NULL;
+ else if (ac->autogenerate_on_missing_class)
+ return alloc_class_assign_by_size(ac, size);
+ else
+ return ac->aclasses[DEFAULT_ALLOC_CLASS_ID];
+ }
+
+ return ac->aclasses[class_id];
+ } else {
+ return ac->aclasses[DEFAULT_ALLOC_CLASS_ID];
+ }
+}
+
+/*
+ * alloc_class_by_run -- returns the allocation class that has the given
+ * unit size
+ */
+struct alloc_class *
+alloc_class_by_run(struct alloc_class_collection *ac,
+ size_t unit_size, uint16_t flags, uint32_t size_idx)
+{
+ size_t map_idx = SIZE_TO_CLASS_MAP_INDEX(unit_size, ac->granularity);
+ ASSERT(map_idx <= UINT32_MAX);
+ uint32_t map_idx_s = (uint32_t)map_idx;
+ ASSERT(size_idx <= UINT16_MAX);
+ uint16_t size_idx_s = (uint16_t)size_idx;
+ uint16_t flags_s = (uint16_t)flags;
+
+ return critnib_get(ac->class_map_by_unit_size,
+ RUN_CLASS_KEY_PACK(map_idx_s, flags_s, size_idx_s));
+}
+
+/*
+ * alloc_class_by_id -- returns the allocation class with an id
+ */
+struct alloc_class *
+alloc_class_by_id(struct alloc_class_collection *ac, uint8_t id)
+{
+ return ac->aclasses[id];
+}
+
+/*
+ * alloc_class_calc_size_idx -- calculates how many units does the size require
+ */
+ssize_t
+alloc_class_calc_size_idx(struct alloc_class *c, size_t size)
+{
+ uint32_t size_idx = CALC_SIZE_IDX(c->unit_size,
+ size + header_type_to_size[c->header_type]);
+
+ if (c->type == CLASS_RUN) {
+ if (c->header_type == HEADER_NONE && size_idx != 1)
+ return -1;
+ else if (size_idx > RUN_UNIT_MAX)
+ return -1;
+ else if (size_idx > c->rdsc.nallocs)
+ return -1;
+ }
+
+ return size_idx;
+}
projects / ceph.git / blobdiff