summaryrefslogtreecommitdiffstats
path: root/sys/kern/subr_unit.c
diff options
context:
space:
mode:
Diffstat (limited to 'sys/kern/subr_unit.c')
-rw-r--r--sys/kern/subr_unit.c79
1 files changed, 40 insertions, 39 deletions
diff --git a/sys/kern/subr_unit.c b/sys/kern/subr_unit.c
index 8283550..f39f001 100644
--- a/sys/kern/subr_unit.c
+++ b/sys/kern/subr_unit.c
@@ -67,13 +67,13 @@
* N is the number of the highest unit allocated.
*/
+#include <sys/param.h>
#include <sys/types.h>
#include <sys/_unrhdr.h>
#ifdef _KERNEL
#include <sys/bitstring.h>
-#include <sys/param.h>
#include <sys/malloc.h>
#include <sys/kernel.h>
#include <sys/systm.h>
@@ -169,7 +169,7 @@ mtx_assert(struct mtx *mp, int flag)
* element:
* If ptr is NULL, it represents a run of free items.
* If ptr points to the unrhdr it represents a run of allocated items.
- * Otherwise it points to an bitstring of allocated items.
+ * Otherwise it points to a bitstring of allocated items.
*
* For runs the len field is the length of the run.
* For bitmaps the len field represents the number of allocated items.
@@ -183,14 +183,33 @@ struct unr {
};
struct unrb {
- u_char busy;
- bitstr_t map[sizeof(struct unr) - 1];
+ bitstr_t map[sizeof(struct unr) / sizeof(bitstr_t)];
};
-CTASSERT(sizeof(struct unr) == sizeof(struct unrb));
+CTASSERT((sizeof(struct unr) % sizeof(bitstr_t)) == 0);
+
+/* Number of bits we can store in the bitmap */
+#define NBITS (8 * sizeof(((struct unrb*)NULL)->map))
+
+/* Is the unrb empty in at least the first len bits? */
+static inline bool
+ub_empty(struct unrb *ub, int len) {
+ int first_set;
+
+ bit_ffs(ub->map, len, &first_set);
+ return (first_set == -1);
+}
+
+/* Is the unrb full? That is, is the number of set elements equal to len? */
+static inline bool
+ub_full(struct unrb *ub, int len)
+{
+ int first_clear;
+
+ bit_ffc(ub->map, len, &first_clear);
+ return (first_clear == -1);
+}
-/* Number of bits in the bitmap */
-#define NBITS ((int)sizeof(((struct unrb *)NULL)->map) * 8)
#if defined(DIAGNOSTIC) || !defined(_KERNEL)
/*
@@ -214,16 +233,13 @@ check_unrhdr(struct unrhdr *uh, int line)
if (up->ptr != uh && up->ptr != NULL) {
ub = up->ptr;
KASSERT (up->len <= NBITS,
- ("UNR inconsistency: len %u max %d (line %d)\n",
+ ("UNR inconsistency: len %u max %zd (line %d)\n",
up->len, NBITS, line));
z++;
w = 0;
for (x = 0; x < up->len; x++)
if (bit_test(ub->map, x))
w++;
- KASSERT (w == ub->busy,
- ("UNR inconsistency: busy %u found %u (line %d)\n",
- ub->busy, w, line));
y += w;
} else if (up->ptr != NULL)
y += up->len;
@@ -239,7 +255,7 @@ check_unrhdr(struct unrhdr *uh, int line)
#else
static __inline void
-check_unrhdr(struct unrhdr *uh, int line)
+check_unrhdr(struct unrhdr *uh __unused, int line __unused)
{
}
@@ -417,32 +433,24 @@ optimize_unr(struct unrhdr *uh)
a = us->len;
l = us->ptr == uh ? 1 : 0;
ub = (void *)us;
- ub->busy = 0;
- if (l) {
+ bit_nclear(ub->map, 0, NBITS - 1);
+ if (l)
bit_nset(ub->map, 0, a);
- ub->busy += a;
- } else {
- bit_nclear(ub->map, 0, a);
- }
if (!is_bitmap(uh, uf)) {
- if (uf->ptr == NULL) {
+ if (uf->ptr == NULL)
bit_nclear(ub->map, a, a + uf->len - 1);
- } else {
+ else
bit_nset(ub->map, a, a + uf->len - 1);
- ub->busy += uf->len;
- }
uf->ptr = ub;
uf->len += a;
us = uf;
} else {
ubf = uf->ptr;
for (l = 0; l < uf->len; l++, a++) {
- if (bit_test(ubf->map, l)) {
+ if (bit_test(ubf->map, l))
bit_set(ub->map, a);
- ub->busy++;
- } else {
+ else
bit_clear(ub->map, a);
- }
}
uf->len = a;
delete_unr(uh, uf->ptr);
@@ -464,19 +472,16 @@ optimize_unr(struct unrhdr *uh)
delete_unr(uh, uf);
} else if (uf->ptr == uh) {
bit_nset(ub->map, us->len, us->len + uf->len - 1);
- ub->busy += uf->len;
us->len += uf->len;
TAILQ_REMOVE(&uh->head, uf, list);
delete_unr(uh, uf);
} else {
ubf = uf->ptr;
for (l = 0; l < uf->len; l++, us->len++) {
- if (bit_test(ubf->map, l)) {
+ if (bit_test(ubf->map, l))
bit_set(ub->map, us->len);
- ub->busy++;
- } else {
+ else
bit_clear(ub->map, us->len);
- }
}
TAILQ_REMOVE(&uh->head, uf, list);
delete_unr(uh, ubf);
@@ -499,10 +504,10 @@ collapse_unr(struct unrhdr *uh, struct unr *up)
/* If bitmap is all set or clear, change it to runlength */
if (is_bitmap(uh, up)) {
ub = up->ptr;
- if (ub->busy == up->len) {
+ if (ub_full(ub, up->len)) {
delete_unr(uh, up->ptr);
up->ptr = uh;
- } else if (ub->busy == 0) {
+ } else if (ub_empty(ub, up->len)) {
delete_unr(uh, up->ptr);
up->ptr = NULL;
}
@@ -600,11 +605,9 @@ alloc_unrl(struct unrhdr *uh)
up->len--;
} else { /* bitmap */
ub = up->ptr;
- KASSERT(ub->busy < up->len, ("UNR bitmap confusion"));
bit_ffc(ub->map, up->len, &y);
KASSERT(y != -1, ("UNR corruption: No clear bit in bitmap."));
bit_set(ub->map, y);
- ub->busy++;
x += y;
}
uh->busy++;
@@ -688,7 +691,6 @@ alloc_unr_specificl(struct unrhdr *uh, u_int item, void **p1, void **p2)
ub = up->ptr;
if (bit_test(ub->map, i) == 0) {
bit_set(ub->map, i);
- ub->busy++;
goto done;
} else
return (-1);
@@ -807,7 +809,6 @@ free_unrl(struct unrhdr *uh, u_int item, void **p1, void **p2)
("UNR: Freeing free item %d (bitmap)\n", item));
bit_clear(ub->map, item);
uh->busy--;
- ub->busy--;
collapse_unr(uh, up);
return;
}
@@ -905,7 +906,7 @@ print_unr(struct unrhdr *uh, struct unr *up)
printf("alloc\n");
else {
ub = up->ptr;
- printf("bitmap(%d) [", ub->busy);
+ printf("bitmap [");
for (x = 0; x < up->len; x++) {
if (bit_test(ub->map, x))
printf("#");
@@ -1025,7 +1026,7 @@ main(int argc, char **argv)
printf("sizeof(struct unr) %zu\n", sizeof(struct unr));
printf("sizeof(struct unrb) %zu\n", sizeof(struct unrb));
printf("sizeof(struct unrhdr) %zu\n", sizeof(struct unrhdr));
- printf("NBITS %d\n", NBITS);
+ printf("NBITS %lu\n", NBITS);
x = 1;
for (m = 0; m < count * reps; m++) {
j = random();
OpenPOWER on IntegriCloud