From 903ea5485765f4f07b9535296b1dfca3775630c7 Mon Sep 17 00:00:00 2001 From: "H. Peter Anvin" Date: Thu, 14 Jun 2018 19:21:12 -0700 Subject: [PATCH] RAA: clean up the RAA infrastructure, make it support larger indicies Make the RAA infrastructure a bit cleaner, make it support 64-bit indicies, and reduce the memory overhead of a sparse or small RAA -- the old code would allocate a *minimum* of 256K for each RAA. The new code reduces that to 16K, and will not mandatorily allocate an entry in the zero position. The new shift, 11, was chosen so that a 32-bit RAA value will need 3 layers and a 64-bit value 6 layers, without excessive waste. Signed-off-by: H. Peter Anvin --- include/raa.h | 11 +++--- nasmlib/raa.c | 120 +++++++++++++++++++++++++++++----------------------------- 2 files changed, 65 insertions(+), 66 deletions(-) diff --git a/include/raa.h b/include/raa.h index 9b636693..e08d90bc 100644 --- a/include/raa.h +++ b/include/raa.h @@ -37,12 +37,13 @@ #include "compiler.h" struct RAA; +typedef uint64_t raaindex; -struct RAA * never_null raa_init(void); +#define raa_init() NULL void raa_free(struct RAA *); -int64_t raa_read(struct RAA *, int32_t); -void *raa_read_ptr(struct RAA *, int32_t); -struct RAA * never_null raa_write(struct RAA *r, int32_t posn, int64_t value); -struct RAA * never_null raa_write_ptr(struct RAA *r, int32_t posn, void *value); +int64_t raa_read(struct RAA *, raaindex); +void *raa_read_ptr(struct RAA *, raaindex); +struct RAA * never_null raa_write(struct RAA *r, raaindex posn, int64_t value); +struct RAA * never_null raa_write_ptr(struct RAA *r, raaindex posn, void *value); #endif /* NASM_RAA_H */ diff --git a/nasmlib/raa.c b/nasmlib/raa.c index dd510dfb..feb86970 100644 --- a/nasmlib/raa.c +++ b/nasmlib/raa.c @@ -33,6 +33,7 @@ #include "nasmlib.h" #include "raa.h" +#include "ilog2.h" /* * Routines to manage a dynamic random access array of int64_ts which @@ -40,10 +41,9 @@ * chunk. */ -#define RAA_BLKSHIFT 15 /* 2**this many longs allocated at once */ -#define RAA_BLKSIZE (1 << RAA_BLKSHIFT) -#define RAA_LAYERSHIFT 15 /* 2**this many _pointers_ allocated */ -#define RAA_LAYERSIZE (1 << RAA_LAYERSHIFT) +#define RAA_LAYERSHIFT 11 /* 2^this many items per layer */ +#define RAA_LAYERSIZE ((size_t)1 << RAA_LAYERSHIFT) +#define RAA_LAYERMASK (RAA_LAYERSIZE-1) typedef struct RAA RAA; typedef union RAA_UNION RAA_UNION; @@ -56,27 +56,32 @@ union intorptr { }; struct RAA { + /* Last position in this RAA */ + raaindex endposn; + /* * Number of layers below this one to get to the real data. 0 - * means this structure is a leaf, holding RAA_BLKSIZE real + * means this structure is a leaf, holding RAA_LAYERSIZE real * data items; 1 and above mean it's a branch, holding * RAA_LAYERSIZE pointers to the next level branch or leaf * structures. */ - int layers; + unsigned int layers; /* * Number of real data items spanned by one position in the * `data' array at this level. This number is 0 trivially, for - * a leaf (level 0): for a level 1 branch it should be - * RAA_BLKSHIFT, and for a level 2 branch it's - * RAA_LAYERSHIFT+RAA_BLKSHIFT. + * a leaf (level 0): for a level n branch it should be + * n*RAA_LAYERSHIFT. */ - int shift; + unsigned int shift; + /* + * The actual data + */ union RAA_UNION { struct RAA_LEAF { - union intorptr data[RAA_BLKSIZE]; + union intorptr data[RAA_LAYERSIZE]; } l; struct RAA_BRANCH { struct RAA *data[RAA_LAYERSIZE]; @@ -87,54 +92,50 @@ struct RAA { #define LEAFSIZ (sizeof(RAA)-sizeof(RAA_UNION)+sizeof(RAA_LEAF)) #define BRANCHSIZ (sizeof(RAA)-sizeof(RAA_UNION)+sizeof(RAA_BRANCH)) -#define LAYERSHIFT(r) ( (r)->layers==0 ? RAA_BLKSHIFT : RAA_LAYERSHIFT ) - -static struct RAA *real_raa_init(int layers) +static struct RAA *raa_init_layer(raaindex posn, unsigned int layers) { struct RAA *r; + raaindex posmask; - if (layers == 0) { - r = nasm_zalloc(LEAFSIZ); - r->shift = 0; - } else { - r = nasm_zalloc(BRANCHSIZ); - r->layers = layers; - r->shift = (RAA_BLKSHIFT - RAA_LAYERSHIFT) + layers * RAA_LAYERSHIFT; - } + r = nasm_zalloc((layers == 0) ? LEAFSIZ : BRANCHSIZ); + r->shift = layers * RAA_LAYERSHIFT; + r->layers = layers; + posmask = ((raaindex)RAA_LAYERSIZE << r->shift) - 1; + r->endposn = posn | posmask; return r; } -struct RAA *raa_init(void) -{ - return real_raa_init(0); -} - void raa_free(struct RAA *r) { + if (!r) + return; + if (r->layers) { - struct RAA **p; - for (p = r->u.b.data; p - r->u.b.data < RAA_LAYERSIZE; p++) - if (*p) - raa_free(*p); + struct RAA **p = r->u.b.data; + size_t i; + for (i = 0; i < RAA_LAYERSIZE; i++) + raa_free(*p++); } nasm_free(r); } -static const union intorptr *real_raa_read(struct RAA *r, int32_t posn) +static const union intorptr *real_raa_read(struct RAA *r, raaindex posn) { - if ((uint32_t) posn >= (UINT32_C(1) << (r->shift + LAYERSHIFT(r)))) + nasm_assert(posn <= (~(raaindex)0 >> 1)); + + if (unlikely(!r || posn > r->endposn)) return NULL; /* Beyond the end */ - while (r->layers > 0) { - int32_t l = posn >> r->shift; - posn &= (UINT32_C(1) << r->shift) - 1; + + while (r->layers) { + size_t l = (posn >> r->shift) & RAA_LAYERMASK; r = r->u.b.data[l]; if (!r) return NULL; /* Not present */ } - return &r->u.l.data[posn]; + return &r->u.l.data[posn & RAA_LAYERMASK]; } -int64_t raa_read(struct RAA *r, int32_t pos) +int64_t raa_read(struct RAA *r, raaindex pos) { const union intorptr *ip; @@ -142,7 +143,7 @@ int64_t raa_read(struct RAA *r, int32_t pos) return ip ? ip->i : 0; } -void *raa_read_ptr(struct RAA *r, int32_t pos) +void *raa_read_ptr(struct RAA *r, raaindex pos) { const union intorptr *ip; @@ -152,43 +153,40 @@ void *raa_read_ptr(struct RAA *r, int32_t pos) static struct RAA * -real_raa_write(struct RAA *r, int32_t posn, union intorptr value) +real_raa_write(struct RAA *r, raaindex posn, union intorptr value) { struct RAA *result; - nasm_assert(posn >= 0); + nasm_assert(posn <= (~(raaindex)0 >> 1)); - while ((UINT32_C(1) << (r->shift + LAYERSHIFT(r))) <= (uint32_t) posn) { - /* - * Must add a layer. - */ - struct RAA *s; - - s = nasm_zalloc(BRANCHSIZ); - s->layers = r->layers + 1; - s->shift = LAYERSHIFT(r) + r->shift; - s->u.b.data[0] = r; - r = s; + if (unlikely(!r)) { + /* Create a new top-level RAA */ + r = raa_init_layer(posn, ilog2_64(posn)/RAA_LAYERSHIFT); + } else { + while (unlikely(r->endposn < posn)) { + /* We need to add layers to an existing RAA */ + struct RAA *s = raa_init_layer(r->endposn, r->layers + 1); + s->u.b.data[0] = r; + r = s; + } } result = r; - while (r->layers > 0) { + while (r->layers) { struct RAA **s; - int32_t l = posn >> r->shift; - posn &= (UINT32_C(1) << r->shift) - 1; + size_t l = (posn >> r->shift) & RAA_LAYERMASK; s = &r->u.b.data[l]; - if (!*s) - *s = real_raa_init(r->layers - 1); + if (unlikely(!*s)) + *s = raa_init_layer(posn, r->layers - 1); r = *s; } - - r->u.l.data[posn] = value; + r->u.l.data[posn & RAA_LAYERMASK] = value; return result; } -struct RAA *raa_write(struct RAA *r, int32_t posn, int64_t value) +struct RAA *raa_write(struct RAA *r, raaindex posn, int64_t value) { union intorptr ip; @@ -196,7 +194,7 @@ struct RAA *raa_write(struct RAA *r, int32_t posn, int64_t value) return real_raa_write(r, posn, ip); } -struct RAA *raa_write_ptr(struct RAA *r, int32_t posn, void *value) +struct RAA *raa_write_ptr(struct RAA *r, raaindex posn, void *value) { union intorptr ip; -- 2.11.4.GIT