Re: svn commit: r324420 - in head/sys: kern sys
On 10/09/2017 10:54, Cy Schubert wrote:
> In message <201710082217.v98mhdni012...@repo.freebsd.org>, Alan Cox writes:
>> Author: alc
>> Date: Sun Oct 8 22:17:39 2017
>> New Revision: 324420
>> URL: https://svnweb.freebsd.org/changeset/base/324420
>>
>> Log:
>> The blst_radix_init function has two purposes - to compute the number of
>> nodes to allocate for the blist, and to initialize them. The computation
>> can be done much more quickly by identifying the terminating node, if any,
>> at every level of the tree and then summing the number of nodes at each
>> level that precedes the topmost terminator. The initialization can also be
>> done quickly, since settings at the root mark the tree as all-allocated, an
>> d
>> only a few terminator nodes need to be marked in the rest of the tree.
>> Eliminate blst_radix_init, and perform its two functions more simply in
>> blist_create.
>>
>> The allocation of the blist takes places in two pieces, but there's no good
>> reason to do so, when a single allocation is sufficient, and simpler.
>> Allocate the blist struct, and the array of nodes associated with it, with
>> a
>> single allocation.
>>
>> Submitted by: Doug Moore
>> Reviewed by: markj (an earlier version)
>> MFC after: 1 week
>> Differential Revision: https://reviews.freebsd.org/D11968
>>
>> Modified:
>> head/sys/kern/subr_blist.c
>> head/sys/sys/blist.h
>>
>> Modified: head/sys/kern/subr_blist.c
>> =
>> =
>> --- head/sys/kern/subr_blist.c Sun Oct 8 21:20:25 2017(r32441
>> 9)
>> +++ head/sys/kern/subr_blist.c Sun Oct 8 22:17:39 2017(r32442
>> 0)
>> @@ -108,6 +108,7 @@ __FBSDID("$FreeBSD$");
>> #include
>> #include
>> #include
>> +#include
>> #include
>> #include
>> #include
>> @@ -137,7 +138,6 @@ static void blst_copy(blmeta_t *scan, daddr_t blk, dad
>> 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 coun
>> t,
>> 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_t
>> 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 th
>> e
>> + * 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]
Re: svn commit: r324420 - in head/sys: kern sys
In message <201710082217.v98mhdni012...@repo.freebsd.org>, Alan Cox writes:
> Author: alc
> Date: Sun Oct 8 22:17:39 2017
> New Revision: 324420
> URL: https://svnweb.freebsd.org/changeset/base/324420
>
> Log:
> The blst_radix_init function has two purposes - to compute the number of
> nodes to allocate for the blist, and to initialize them. The computation
> can be done much more quickly by identifying the terminating node, if any,
> at every level of the tree and then summing the number of nodes at each
> level that precedes the topmost terminator. The initialization can also be
> done quickly, since settings at the root mark the tree as all-allocated, an
> d
> only a few terminator nodes need to be marked in the rest of the tree.
> Eliminate blst_radix_init, and perform its two functions more simply in
> blist_create.
>
> The allocation of the blist takes places in two pieces, but there's no good
> reason to do so, when a single allocation is sufficient, and simpler.
> Allocate the blist struct, and the array of nodes associated with it, with
> a
> single allocation.
>
> Submitted by: Doug Moore
> Reviewed by:markj (an earlier version)
> MFC after: 1 week
> Differential Revision: https://reviews.freebsd.org/D11968
>
> Modified:
> head/sys/kern/subr_blist.c
> head/sys/sys/blist.h
>
> Modified: head/sys/kern/subr_blist.c
> =
> =
> --- head/sys/kern/subr_blist.cSun Oct 8 21:20:25 2017(r32441
> 9)
> +++ head/sys/kern/subr_blist.cSun Oct 8 22:17:39 2017(r32442
> 0)
> @@ -108,6 +108,7 @@ __FBSDID("$FreeBSD$");
> #include
> #include
> #include
> +#include
> #include
> #include
> #include
> @@ -137,7 +138,6 @@ static void blst_copy(blmeta_t *scan, daddr_t blk, dad
> 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 coun
> t,
> 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_t
> 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 th
> e
> + * 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;
> +
svn commit: r324420 - in head/sys: kern sys
Author: alc
Date: Sun Oct 8 22:17:39 2017
New Revision: 324420
URL: https://svnweb.freebsd.org/changeset/base/324420
Log:
The blst_radix_init function has two purposes - to compute the number of
nodes to allocate for the blist, and to initialize them. The computation
can be done much more quickly by identifying the terminating node, if any,
at every level of the tree and then summing the number of nodes at each
level that precedes the topmost terminator. The initialization can also be
done quickly, since settings at the root mark the tree as all-allocated, and
only a few terminator nodes need to be marked in the rest of the tree.
Eliminate blst_radix_init, and perform its two functions more simply in
blist_create.
The allocation of the blist takes places in two pieces, but there's no good
reason to do so, when a single allocation is sufficient, and simpler.
Allocate the blist struct, and the array of nodes associated with it, with a
single allocation.
Submitted by: Doug Moore
Reviewed by: markj (an earlier version)
MFC after:1 week
Differential Revision:https://reviews.freebsd.org/D11968
Modified:
head/sys/kern/subr_blist.c
head/sys/sys/blist.h
Modified: head/sys/kern/subr_blist.c
==
--- head/sys/kern/subr_blist.c Sun Oct 8 21:20:25 2017(r324419)
+++ head/sys/kern/subr_blist.c Sun Oct 8 22:17:39 2017(r324420)
@@ -108,6 +108,7 @@ __FBSDID("$FreeBSD$");
#include
#include
#include
+#include
#include
#include
#include
@@ -137,7 +138,6 @@ static void blst_copy(blmeta_t *scan, daddr_t blk, dad
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 voidblst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix,
int tab);
@@ -218,30 +218,69 @@ blist_t
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 @@ blist_create(daddr_t blocks, int flags)
void
blist_de
