Source-Changes-HG archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
[src/trunk]: src/sys introduce new types, blist_bitmap_t and blist_blkno_t,
details: https://anonhg.NetBSD.org/src/rev/69c6c8208d28
branches: trunk
changeset: 580046:69c6c8208d28
user: yamt <yamt%NetBSD.org@localhost>
date: Wed Apr 06 13:09:10 2005 +0000
description:
introduce new types, blist_bitmap_t and blist_blkno_t,
and use them instead of uint64_t.
make them 32-bit for now because it's what swap slot allocation code uses.
diffstat:
sys/kern/subr_blist.c | 298 +++++++++++++++++++++++++++----------------------
sys/sys/blist.h | 21 ++-
2 files changed, 175 insertions(+), 144 deletions(-)
diffs (truncated from 709 to 300 lines):
diff -r 1e64fc72e199 -r 69c6c8208d28 sys/kern/subr_blist.c
--- a/sys/kern/subr_blist.c Wed Apr 06 11:36:37 2005 +0000
+++ b/sys/kern/subr_blist.c Wed Apr 06 13:09:10 2005 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: subr_blist.c,v 1.4 2005/04/06 11:36:37 yamt Exp $ */
+/* $NetBSD: subr_blist.c,v 1.5 2005/04/06 13:09:10 yamt Exp $ */
/*-
* Copyright (c) 1998 Matthew Dillon. All Rights Reserved.
@@ -86,7 +86,7 @@
*/
#include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: subr_blist.c,v 1.4 2005/04/06 11:36:37 yamt Exp $");
+__KERNEL_RCSID(0, "$NetBSD: subr_blist.c,v 1.5 2005/04/06 13:09:10 yamt Exp $");
#if 0
__FBSDID("$FreeBSD: src/sys/kern/subr_blist.c,v 1.17 2004/06/04 04:03:25 alc Exp $");
#endif
@@ -129,19 +129,19 @@
typedef struct blmeta {
union {
- uint64_t bmu_avail; /* space available under us */
- uint64_t bmu_bitmap; /* bitmap if we are a leaf */
+ blist_blkno_t bmu_avail; /* space available under us */
+ blist_bitmap_t bmu_bitmap; /* bitmap if we are a leaf */
} u;
- uint64_t bm_bighint; /* biggest contiguous block hint*/
+ blist_blkno_t bm_bighint; /* biggest contiguous block hint*/
} blmeta_t;
struct blist {
- uint64_t bl_blocks; /* area of coverage */
- uint64_t bl_radix; /* coverage radix */
- uint64_t bl_skip; /* starting skip */
- uint64_t bl_free; /* number of free blocks */
+ blist_blkno_t bl_blocks; /* area of coverage */
+ blist_blkno_t bl_radix; /* coverage radix */
+ blist_blkno_t bl_skip; /* starting skip */
+ blist_blkno_t bl_free; /* number of free blocks */
blmeta_t *bl_root; /* root of radix tree */
- uint64_t bl_rootblks; /* blks allocated for tree */
+ blist_blkno_t bl_rootblks; /* blks allocated for tree */
};
#define BLIST_META_RADIX 16
@@ -150,22 +150,25 @@
* static support functions
*/
-static uint64_t blst_leaf_alloc(blmeta_t *scan, uint64_t blk, int count);
-static uint64_t blst_meta_alloc(blmeta_t *scan, uint64_t blk,
- uint64_t count, uint64_t radix, int skip);
-static void blst_leaf_free(blmeta_t *scan, uint64_t relblk, int count);
-static void blst_meta_free(blmeta_t *scan, uint64_t freeBlk, uint64_t count,
- uint64_t radix, int skip, uint64_t blk);
-static void blst_copy(blmeta_t *scan, uint64_t blk, uint64_t radix,
- uint64_t skip, blist_t dest, uint64_t count);
-static int blst_leaf_fill(blmeta_t *scan, uint64_t blk, int count);
-static int blst_meta_fill(blmeta_t *scan, uint64_t allocBlk, uint64_t count,
- uint64_t radix, int skip, uint64_t blk);
-static uint64_t blst_radix_init(blmeta_t *scan, uint64_t radix,
- int skip, uint64_t count);
+static blist_blkno_t blst_leaf_alloc(blmeta_t *scan, blist_blkno_t blk,
+ int count);
+static blist_blkno_t blst_meta_alloc(blmeta_t *scan, blist_blkno_t blk,
+ blist_blkno_t count, blist_blkno_t radix, blist_blkno_t skip);
+static void blst_leaf_free(blmeta_t *scan, blist_blkno_t relblk, int count);
+static void blst_meta_free(blmeta_t *scan, blist_blkno_t freeBlk,
+ blist_blkno_t count, blist_blkno_t radix, blist_blkno_t skip,
+ blist_blkno_t blk);
+static void blst_copy(blmeta_t *scan, blist_blkno_t blk, blist_blkno_t radix,
+ blist_blkno_t skip, blist_t dest, blist_blkno_t count);
+static int blst_leaf_fill(blmeta_t *scan, blist_blkno_t blk, int count);
+static blist_blkno_t blst_meta_fill(blmeta_t *scan, blist_blkno_t allocBlk,
+ blist_blkno_t count, blist_blkno_t radix, blist_blkno_t skip,
+ blist_blkno_t blk);
+static blist_blkno_t blst_radix_init(blmeta_t *scan, blist_blkno_t radix,
+ blist_blkno_t skip, blist_blkno_t count);
#ifndef _KERNEL
-static void blst_radix_print(blmeta_t *scan, uint64_t blk,
- uint64_t radix, int skip, int tab);
+static void blst_radix_print(blmeta_t *scan, blist_blkno_t blk,
+ blist_blkno_t radix, blist_blkno_t skip, int tab);
#endif
#ifdef _KERNEL
@@ -183,14 +186,16 @@
*/
blist_t
-blist_create(uint64_t blocks)
+blist_create(blist_blkno_t blocks)
{
blist_t bl;
- int radix;
- int skip = 0;
+ blist_blkno_t radix;
+ blist_blkno_t skip = 0;
/*
* Calculate radix and skip field used for scanning.
+ *
+ * XXX check overflow
*/
radix = BLIST_BMAP_RADIX;
@@ -212,12 +217,12 @@
printf(
"BLIST representing %" PRIu64 " blocks (%" PRIu64 " MB of swap)"
", requiring %" PRIu64 "K of ram\n",
- bl->bl_blocks,
- bl->bl_blocks * 4 / 1024,
- (bl->bl_rootblks * sizeof(blmeta_t) + 1023) / 1024
+ (uint64_t)bl->bl_blocks,
+ (uint64_t)bl->bl_blocks * 4 / 1024,
+ ((uint64_t)bl->bl_rootblks * sizeof(blmeta_t) + 1023) / 1024
);
printf("BLIST raw radix tree contains %" PRIu64 " records\n",
- bl->bl_rootblks);
+ (uint64_t)bl->bl_rootblks);
#endif
blst_radix_init(bl->bl_root, bl->bl_radix, bl->bl_skip, blocks);
@@ -237,10 +242,10 @@
* not be allocated.
*/
-uint64_t
-blist_alloc(blist_t bl, uint64_t count)
+blist_blkno_t
+blist_alloc(blist_t bl, blist_blkno_t count)
{
- uint64_t blk = BLIST_NONE;
+ blist_blkno_t blk = BLIST_NONE;
if (bl) {
if (bl->bl_radix == BLIST_BMAP_RADIX)
@@ -260,7 +265,7 @@
*/
void
-blist_free(blist_t bl, uint64_t blkno, uint64_t count)
+blist_free(blist_t bl, blist_blkno_t blkno, blist_blkno_t count)
{
if (bl) {
if (bl->bl_radix == BLIST_BMAP_RADIX)
@@ -278,10 +283,10 @@
* actually filled that were free before the call.
*/
-int
-blist_fill(blist_t bl, uint64_t blkno, uint64_t count)
+blist_blkno_t
+blist_fill(blist_t bl, blist_blkno_t blkno, blist_blkno_t count)
{
- int filled;
+ blist_blkno_t filled;
if (bl) {
if (bl->bl_radix == BLIST_BMAP_RADIX)
@@ -304,7 +309,7 @@
*/
void
-blist_resize(blist_t *pbl, uint64_t count, int freenew)
+blist_resize(blist_t *pbl, blist_blkno_t count, int freenew)
{
blist_t newbl = blist_create(count);
blist_t save = *pbl;
@@ -358,13 +363,13 @@
* quick.
*/
-static uint64_t
+static blist_blkno_t
blst_leaf_alloc(
blmeta_t *scan,
- uint64_t blk,
+ blist_blkno_t blk,
int count
) {
- uint64_t orig = scan->u.bmu_bitmap;
+ blist_bitmap_t orig = scan->u.bmu_bitmap;
if (orig == 0) {
/*
@@ -379,11 +384,11 @@
/*
* Optimized code to allocate one bit out of the bitmap
*/
- uint64_t mask;
+ blist_bitmap_t mask;
int j = BLIST_BMAP_RADIX/2;
int r = 0;
- mask = (uint64_t)-1 >> (BLIST_BMAP_RADIX/2);
+ mask = (blist_bitmap_t)-1 >> (BLIST_BMAP_RADIX/2);
while (j) {
if ((orig & mask) == 0) {
@@ -393,7 +398,7 @@
j >>= 1;
mask >>= j;
}
- scan->u.bmu_bitmap &= ~((uint64_t)1 << r);
+ scan->u.bmu_bitmap &= ~((blist_bitmap_t)1 << r);
return(blk + r);
}
if (count <= BLIST_BMAP_RADIX) {
@@ -406,9 +411,9 @@
*/
int j;
int n = BLIST_BMAP_RADIX - count;
- uint64_t mask;
+ blist_bitmap_t mask;
- mask = (uint64_t)-1 >> n;
+ mask = (blist_bitmap_t)-1 >> n;
for (j = 0; j <= n; ++j) {
if ((orig & mask) == mask) {
@@ -434,16 +439,16 @@
* and we have a few optimizations strewn in as well.
*/
-static uint64_t
+static blist_blkno_t
blst_meta_alloc(
blmeta_t *scan,
- uint64_t blk,
- uint64_t count,
- uint64_t radix,
- int skip
+ blist_blkno_t blk,
+ blist_blkno_t count,
+ blist_blkno_t radix,
+ blist_blkno_t skip
) {
- int i;
- int next_skip = ((u_int)skip / BLIST_META_RADIX);
+ blist_blkno_t i;
+ blist_blkno_t next_skip = (skip / BLIST_META_RADIX);
if (scan->u.bmu_avail == 0) {
/*
@@ -461,10 +466,10 @@
* sublevel.
*/
for (i = 1; i <= skip; i += next_skip) {
- if (scan[i].bm_bighint == (uint64_t)-1)
+ if (scan[i].bm_bighint == (blist_blkno_t)-1)
break;
if (next_skip == 1) {
- scan[i].u.bmu_bitmap = (uint64_t)-1;
+ scan[i].u.bmu_bitmap = (blist_bitmap_t)-1;
scan[i].bm_bighint = BLIST_BMAP_RADIX;
} else {
scan[i].bm_bighint = radix;
@@ -476,7 +481,7 @@
}
for (i = 1; i <= skip; i += next_skip) {
- if (scan[i].bm_bighint == (uint64_t)-1) {
+ if (scan[i].bm_bighint == (blist_blkno_t)-1) {
/*
* Terminator
*/
@@ -485,7 +490,7 @@
/*
* count fits in object
*/
- uint64_t r;
+ blist_blkno_t r;
if (next_skip == 1) {
r = blst_leaf_alloc(&scan[i], blk, count);
} else {
@@ -523,7 +528,7 @@
static void
blst_leaf_free(
blmeta_t *scan,
- uint64_t blk,
+ blist_blkno_t blk,
int count
) {
/*
@@ -535,10 +540,10 @@
* v n
*/
int n = blk & (BLIST_BMAP_RADIX - 1);
- uint64_t mask;
+ blist_bitmap_t mask;
- mask = ((uint64_t)-1 << n) &
- ((uint64_t)-1 >> (BLIST_BMAP_RADIX - count - n));
+ mask = ((blist_bitmap_t)-1 << n) &
+ ((blist_bitmap_t)-1 >> (BLIST_BMAP_RADIX - count - n));
if (scan->u.bmu_bitmap & mask)
panic("blst_radix_free: freeing free block");
Home |
Main Index |
Thread Index |
Old Index