+static inline int
+arena_chunk_dirty_comp(arena_chunk_t *a, arena_chunk_t *b)
+{
+
+ assert(a != NULL);
+ assert(b != NULL);
+
+ /*
+ * Short-circuit for self comparison. The following comparison code
+ * would come to the same result, but at the cost of executing the slow
+ * path.
+ */
+ if (a == b)
+ return (0);
+
+ /*
+ * Order such that chunks with higher fragmentation are "less than"
+ * those with lower fragmentation -- purging order is from "least" to
+ * "greatest". Fragmentation is measured as:
+ *
+ * mean current avail run size
+ * --------------------------------
+ * mean defragmented avail run size
+ *
+ * navail
+ * -----------
+ * nruns_avail nruns_avail-nruns_adjac
+ * = ========================= = -----------------------
+ * navail nruns_avail
+ * -----------------------
+ * nruns_avail-nruns_adjac
+ *
+ * The following code multiplies away the denominator prior to
+ * comparison, in order to avoid division.
+ *
+ */
+ {
+ size_t a_val = (a->nruns_avail - a->nruns_adjac) *
+ b->nruns_avail;
+ size_t b_val = (b->nruns_avail - b->nruns_adjac) *
+ a->nruns_avail;
+
+ if (a_val < b_val)
+ return (1);
+ if (a_val > b_val)
+ return (-1);
+ }
+ /*
+ * Break ties by chunk address. For fragmented chunks, report lower
+ * addresses as "lower", so that fragmentation reduction happens first
+ * at lower addresses. However, use the opposite ordering for
+ * unfragmented chunks, in order to increase the chances of
+ * re-allocating dirty runs.
+ */
+ {
+ uintptr_t a_chunk = (uintptr_t)a;
+ uintptr_t b_chunk = (uintptr_t)b;
+ int ret = ((a_chunk > b_chunk) - (a_chunk < b_chunk));
+ if (a->nruns_adjac == 0) {
+ assert(b->nruns_adjac == 0);
+ ret = -ret;
+ }
+ return (ret);
+ }
+}
+
+/* Generate red-black tree functions. */
+rb_gen(static UNUSED, arena_chunk_dirty_, arena_chunk_tree_t, arena_chunk_t,
+ dirty_link, arena_chunk_dirty_comp)
+
+static inline bool
+arena_avail_adjac_pred(arena_chunk_t *chunk, size_t pageind)
+{
+ bool ret;
+
+ if (pageind-1 < map_bias)
+ ret = false;
+ else {
+ ret = (arena_mapbits_allocated_get(chunk, pageind-1) == 0);
+ assert(ret == false || arena_mapbits_dirty_get(chunk,
+ pageind-1) != arena_mapbits_dirty_get(chunk, pageind));
+ }
+ return (ret);
+}
+
+static inline bool
+arena_avail_adjac_succ(arena_chunk_t *chunk, size_t pageind, size_t npages)
+{
+ bool ret;
+
+ if (pageind+npages == chunk_npages)
+ ret = false;
+ else {
+ assert(pageind+npages < chunk_npages);
+ ret = (arena_mapbits_allocated_get(chunk, pageind+npages) == 0);
+ assert(ret == false || arena_mapbits_dirty_get(chunk, pageind)
+ != arena_mapbits_dirty_get(chunk, pageind+npages));
+ }
+ return (ret);
+}
+
+static inline bool
+arena_avail_adjac(arena_chunk_t *chunk, size_t pageind, size_t npages)
+{
+
+ return (arena_avail_adjac_pred(chunk, pageind) ||
+ arena_avail_adjac_succ(chunk, pageind, npages));
+}
+
+static void
+arena_avail_insert(arena_t *arena, arena_chunk_t *chunk, size_t pageind,
+ size_t npages, bool maybe_adjac_pred, bool maybe_adjac_succ)
+{
+
+ assert(npages == (arena_mapbits_unallocated_size_get(chunk, pageind) >>
+ LG_PAGE));
+
+ /*
+ * chunks_dirty is keyed by nruns_{avail,adjac}, so the chunk must be
+ * removed and reinserted even if the run to be inserted is clean.
+ */
+ if (chunk->ndirty != 0)
+ arena_chunk_dirty_remove(&arena->chunks_dirty, chunk);
+
+ if (maybe_adjac_pred && arena_avail_adjac_pred(chunk, pageind))
+ chunk->nruns_adjac++;
+ if (maybe_adjac_succ && arena_avail_adjac_succ(chunk, pageind, npages))
+ chunk->nruns_adjac++;
+ chunk->nruns_avail++;
+ assert(chunk->nruns_avail > chunk->nruns_adjac);
+
+ if (arena_mapbits_dirty_get(chunk, pageind) != 0) {
+ arena->ndirty += npages;
+ chunk->ndirty += npages;
+ }
+ if (chunk->ndirty != 0)
+ arena_chunk_dirty_insert(&arena->chunks_dirty, chunk);
+
+ arena_avail_tree_insert(&arena->runs_avail, arena_mapp_get(chunk,
+ pageind));
+}
+
+static void
+arena_avail_remove(arena_t *arena, arena_chunk_t *chunk, size_t pageind,
+ size_t npages, bool maybe_adjac_pred, bool maybe_adjac_succ)
+{
+
+ assert(npages == (arena_mapbits_unallocated_size_get(chunk, pageind) >>
+ LG_PAGE));
+
+ /*
+ * chunks_dirty is keyed by nruns_{avail,adjac}, so the chunk must be
+ * removed and reinserted even if the run to be removed is clean.
+ */
+ if (chunk->ndirty != 0)
+ arena_chunk_dirty_remove(&arena->chunks_dirty, chunk);
+
+ if (maybe_adjac_pred && arena_avail_adjac_pred(chunk, pageind))
+ chunk->nruns_adjac--;
+ if (maybe_adjac_succ && arena_avail_adjac_succ(chunk, pageind, npages))
+ chunk->nruns_adjac--;
+ chunk->nruns_avail--;
+ assert(chunk->nruns_avail > chunk->nruns_adjac || (chunk->nruns_avail
+ == 0 && chunk->nruns_adjac == 0));
+
+ if (arena_mapbits_dirty_get(chunk, pageind) != 0) {
+ arena->ndirty -= npages;
+ chunk->ndirty -= npages;
+ }
+ if (chunk->ndirty != 0)
+ arena_chunk_dirty_insert(&arena->chunks_dirty, chunk);
+
+ arena_avail_tree_remove(&arena->runs_avail, arena_mapp_get(chunk,
+ pageind));
+}
+
projects / redis.git / commitdiff
