Page MenuHomeFreeBSD
Files F109604772

D11968.diff
No OneTemporary
Actions

D11968.diff
View Options

Index: head/sys/kern/subr_blist.c
===================================================================
--- head/sys/kern/subr_blist.c
+++ head/sys/kern/subr_blist.c
@@ -108,6 +108,7 @@
#include <sys/sbuf.h>
#include <stdio.h>
#include <string.h>
+#include <stddef.h>
#include <stdlib.h>
#include <stdarg.h>
#include <stdbool.h>
@@ -137,7 +138,6 @@
static daddr_t blst_leaf_fill(blmeta_t *scan, daddr_t blk, int count);
static daddr_t blst_meta_fill(blmeta_t *scan, daddr_t allocBlk, daddr_t count,
u_daddr_t radix);
-static daddr_t blst_radix_init(blmeta_t *scan, daddr_t radix, daddr_t count);
#ifndef _KERNEL
static void blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix,
int tab);
@@ -218,30 +218,69 @@
blist_create(daddr_t blocks, int flags)
{
blist_t bl;
- daddr_t nodes, radix;
+ daddr_t i, last_block;
+ u_daddr_t nodes, radix, skip;
+ int digit;
/*
- * Calculate the radix field used for scanning.
+ * Calculate the radix and node count used for scanning. Find the last
+ * block that is followed by a terminator.
*/
+ last_block = blocks - 1;
radix = BLIST_BMAP_RADIX;
while (radix < blocks) {
+ if (((last_block / radix + 1) & BLIST_META_MASK) != 0)
+ /*
+ * A terminator will be added. Update last_block to the
+ * position just before that terminator.
+ */
+ last_block |= radix - 1;
radix *= BLIST_META_RADIX;
}
- nodes = 1 + blst_radix_init(NULL, radix, blocks);
- bl = malloc(sizeof(struct blist), M_SWAP, flags);
+ /*
+ * Count the meta-nodes in the expanded tree, including the final
+ * terminator, from the bottom level up to the root.
+ */
+ nodes = (last_block >= blocks) ? 2 : 1;
+ last_block /= BLIST_BMAP_RADIX;
+ while (last_block > 0) {
+ nodes += last_block + 1;
+ last_block /= BLIST_META_RADIX;
+ }
+ bl = malloc(offsetof(struct blist, bl_root[nodes]), M_SWAP, flags);
if (bl == NULL)
return (NULL);
bl->bl_blocks = blocks;
bl->bl_radix = radix;
bl->bl_cursor = 0;
- bl->bl_root = malloc(nodes * sizeof(blmeta_t), M_SWAP, flags);
- if (bl->bl_root == NULL) {
- free(bl, M_SWAP);
- return (NULL);
+
+ /*
+ * Initialize the empty tree by filling in root values, then initialize
+ * just the terminators in the rest of the tree.
+ */
+ bl->bl_root[0].bm_bighint = 0;
+ if (radix == BLIST_BMAP_RADIX)
+ bl->bl_root[0].u.bmu_bitmap = 0;
+ else
+ bl->bl_root[0].u.bmu_avail = 0;
+ last_block = blocks - 1;
+ i = 0;
+ while (radix > BLIST_BMAP_RADIX) {
+ radix /= BLIST_META_RADIX;
+ skip = radix_to_skip(radix);
+ digit = last_block / radix;
+ i += 1 + digit * skip;
+ if (digit != BLIST_META_MASK) {
+ /*
+ * Add a terminator.
+ */
+ bl->bl_root[i + skip].bm_bighint = (daddr_t)-1;
+ bl->bl_root[i + skip].u.bmu_bitmap = 0;
+ }
+ last_block %= radix;
}
- blst_radix_init(bl->bl_root, radix, blocks);
#if defined(BLIST_DEBUG)
printf(
@@ -261,7 +300,7 @@
void
blist_destroy(blist_t bl)
{
- free(bl->bl_root, M_SWAP);
+
free(bl, M_SWAP);
}
@@ -1070,83 +1109,6 @@
}
scan->u.bmu_avail -= nblks;
return (nblks);
-}
-
-/*
- * BLST_RADIX_INIT() - initialize radix tree
- *
- * Initialize our meta structures and bitmaps and calculate the exact
- * amount of space required to manage 'count' blocks - this space may
- * be considerably less than the calculated radix due to the large
- * RADIX values we use.
- */
-static daddr_t
-blst_radix_init(blmeta_t *scan, daddr_t radix, daddr_t count)
-{
- daddr_t i, memindex, next_skip, skip;
-
- memindex = 0;
-
- /*
- * Leaf node
- */
-
- if (radix == BLIST_BMAP_RADIX) {
- if (scan) {
- scan->bm_bighint = 0;
- scan->u.bmu_bitmap = 0;
- }
- return (memindex);
- }
-
- /*
- * Meta node. If allocating the entire object we can special
- * case it. However, we need to figure out how much memory
- * is required to manage 'count' blocks, so we continue on anyway.
- */
-
- if (scan) {
- scan->bm_bighint = 0;
- scan->u.bmu_avail = 0;
- }
-
- skip = radix_to_skip(radix);
- next_skip = skip / BLIST_META_RADIX;
- radix /= BLIST_META_RADIX;
-
- for (i = 1; i < skip; i += next_skip) {
- if (count >= radix) {
- /*
- * Allocate the entire object
- */
- memindex = i +
- blst_radix_init(((scan) ? &scan[i] : NULL), radix,
- radix);
- count -= radix;
- } else if (count > 0) {
- /*
- * Allocate a partial object
- */
- memindex = i +
- blst_radix_init(((scan) ? &scan[i] : NULL), radix,
- count);
- count = 0;
- } else {
- /*
- * Add terminator and break out. Make terminator bitmap
- * zero to avoid a spanning leaf allocation that
- * includes the terminator.
- */
- if (scan) {
- scan[i].bm_bighint = (daddr_t)-1;
- scan[i].u.bmu_bitmap = 0;
- }
- break;
- }
- }
- if (memindex < i)
- memindex = i;
- return (memindex);
}
#ifdef BLIST_DEBUG
Index: head/sys/sys/blist.h
===================================================================
--- head/sys/sys/blist.h
+++ head/sys/sys/blist.h
@@ -82,7 +82,7 @@
daddr_t bl_blocks; /* area of coverage */
u_daddr_t bl_radix; /* coverage radix */
daddr_t bl_cursor; /* next-fit search starts at */
- blmeta_t *bl_root; /* root of radix tree */
+ blmeta_t bl_root[1]; /* root of radix tree */
} *blist_t;
#define BLIST_META_RADIX 16

File Metadata

Mime Type
text/plain
Expires
Sat, Feb 8, 8:11 AM (10 h, 21 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
16524005
Default Alt Text
D11968.diff (5 KB)

Event Timeline