From 31c3ffda2848f054f38e2e590ed853f201b7a5e0 Mon Sep 17 00:00:00 2001 From: semarie Date: Sat, 13 Aug 2022 16:02:15 +0000 Subject: [PATCH] blist: fix a possible blist corruption with blist_alloc() due to unsigned swblk_t on OpenBSD. reorder if condition in blst_meta_alloc(), in order to check if the node is 'Terminator' node first (and leave the loop). DragonFlyBSD is unaffected by it as swblk_t is signed (and the first condition isn't taken). add a regress test for it. while here, more the KASSERT() to KDASSERT(). it is useful but only with DEBUG. ok miod@ todd@ --- regress/sys/uvm/blist/Makefile | 7 ++-- regress/sys/uvm/blist/test-6.in | 6 +++ regress/sys/uvm/blist/test-6.out | 20 ++++++++++ sys/kern/subr_blist.c | 64 ++++++++++++++++++++++---------- 4 files changed, 74 insertions(+), 23 deletions(-) create mode 100644 regress/sys/uvm/blist/test-6.in create mode 100644 regress/sys/uvm/blist/test-6.out diff --git a/regress/sys/uvm/blist/Makefile b/regress/sys/uvm/blist/Makefile index c46e70b6c27..0098c3f1d0e 100644 --- a/regress/sys/uvm/blist/Makefile +++ b/regress/sys/uvm/blist/Makefile @@ -1,4 +1,4 @@ -# $OpenBSD: Makefile,v 1.1 2022/07/29 17:47:11 semarie Exp $ +# $OpenBSD: Makefile,v 1.2 2022/08/13 16:02:15 semarie Exp $ SRCS += ${.CURDIR}/../../../../sys/kern/subr_blist.c WARNINGS = Yes @@ -8,7 +8,8 @@ TESTS += \ test-2 1024 \ test-3 64 \ test-4 64 \ - test-5 1024 + test-5 1024 \ + test-6 128 .for t s in ${TESTS} run-$t: blist @@ -27,7 +28,7 @@ CLEANFILES += $t.run .endfor blist: ${SRCS} - ${CC} -o $@ ${CFLAGS} ${SRCS} + ${CC} -g -o $@ ${CFLAGS} ${SRCS} CLEANFILES += blist blist.d regen: ${REGEN_TARGETS} diff --git a/regress/sys/uvm/blist/test-6.in b/regress/sys/uvm/blist/test-6.in new file mode 100644 index 00000000000..ce10210eb75 --- /dev/null +++ b/regress/sys/uvm/blist/test-6.in @@ -0,0 +1,6 @@ +# allocate more than free blocks +a 64 +a 32 +a 64 +p +g diff --git a/regress/sys/uvm/blist/test-6.out b/regress/sys/uvm/blist/test-6.out new file mode 100644 index 00000000000..1f5c7f0655a --- /dev/null +++ b/regress/sys/uvm/blist/test-6.out @@ -0,0 +1,20 @@ +BLIST representing 128 blocks (0 MB of swap), requiring 0.00M of ram +BLIST raw radix tree: 4 records, top-radix 2048 +128/128/2048> 128/128/2048> count 64 +blist_meta_alloc blkat 0 blk 0 count 64 radix 2048 + R=0000 +64/128/2048> count 32 +blist_meta_alloc blkat 0 blk 0 count 32 radix 2048 + R=0040 +32/128/2048> count 64 +blist_meta_alloc blkat 0 blk 0 count 64 radix 2048 + R=SWAPBLK_NONE +32/128/2048> BLIST { + (0000,2048): subtree (32/2048) big=32 { + (0000,64): bitmap 0000000000000000 big=0 + (0040,64): bitmap ffffffff00000000 big=63 + (0080,64): Terminator + } +} +32/128/2048> gapfind: begin=0000 end=0000 size=0 +32/128/2048> \ No newline at end of file diff --git a/sys/kern/subr_blist.c b/sys/kern/subr_blist.c index fdceb294d8f..b0e74b36b6a 100644 --- a/sys/kern/subr_blist.c +++ b/sys/kern/subr_blist.c @@ -1,4 +1,4 @@ -/* $OpenBSD: subr_blist.c,v 1.2 2022/08/06 13:44:04 semarie Exp $ */ +/* $OpenBSD: subr_blist.c,v 1.3 2022/08/13 16:02:15 semarie Exp $ */ /* DragonFlyBSD:7b80531f545c7d3c51c1660130c71d01f6bccbe0:/sys/kern/subr_blist.c */ /* * BLIST.C - Bitmap allocator/deallocator, using a radix tree with hinting @@ -123,6 +123,7 @@ #define mallocarray(n,s,t,f) reallocarray(NULL, n, s) #define free(p,t,s) free(p) #define KASSERT(exp) assert(exp) +#define KDASSERT(exp) assert(exp) #include "../sys/blist.h" @@ -248,8 +249,12 @@ blist_alloc(blist_t bl, swblk_t count) else blk = blst_meta_alloc(bl->bl_root, 0, 0, count, bl->bl_radix, bl->bl_skip); - if (blk != SWAPBLK_NONE) + if (blk != SWAPBLK_NONE) { bl->bl_free -= count; + + KDASSERT(blk < bl->bl_blocks); + KDASSERT(bl->bl_free <= bl->bl_blocks); + } } return(blk); } @@ -260,16 +265,20 @@ blist_allocat(blist_t bl, swblk_t count, swblk_t blkat) swblk_t blk = SWAPBLK_NONE; if (bl) { - KASSERT(blkat < bl->bl_blocks); - KASSERT(blkat + count <= bl->bl_blocks); + KDASSERT(blkat < bl->bl_blocks); + KDASSERT(blkat + count <= bl->bl_blocks); if (bl->bl_radix == BLIST_BMAP_RADIX) blk = blst_leaf_alloc(bl->bl_root, blkat, 0, count); else blk = blst_meta_alloc(bl->bl_root, blkat, 0, count, bl->bl_radix, bl->bl_skip); - if (blk != SWAPBLK_NONE) + if (blk != SWAPBLK_NONE) { bl->bl_free -= count; + + KDASSERT(blk < bl->bl_blocks); + KDASSERT(bl->bl_free <= bl->bl_blocks); + } } return(blk); } @@ -284,14 +293,16 @@ void blist_free(blist_t bl, swblk_t blkno, swblk_t count) { if (bl) { - KASSERT(blkno < bl->bl_blocks); - KASSERT(blkno + count <= bl->bl_blocks); + KDASSERT(blkno < bl->bl_blocks); + KDASSERT(blkno + count <= bl->bl_blocks); if (bl->bl_radix == BLIST_BMAP_RADIX) blst_leaf_free(bl->bl_root, blkno, count); else blst_meta_free(bl->bl_root, blkno, count, bl->bl_radix, bl->bl_skip, 0); bl->bl_free += count; + + KDASSERT(bl->bl_free <= bl->bl_blocks); } } @@ -308,9 +319,9 @@ blist_fill(blist_t bl, swblk_t blkno, swblk_t count) swblk_t filled; if (bl) { - KASSERT(blkno < bl->bl_blocks); - KASSERT(blkno + count <= bl->bl_blocks); - + KDASSERT(blkno < bl->bl_blocks); + KDASSERT(blkno + count <= bl->bl_blocks); + if (bl->bl_radix == BLIST_BMAP_RADIX) { filled = blst_leaf_fill(bl->bl_root, blkno, count); } else { @@ -318,6 +329,7 @@ blist_fill(blist_t bl, swblk_t blkno, swblk_t count) bl->bl_radix, bl->bl_skip, 0); } bl->bl_free -= filled; + KDASSERT(bl->bl_free <= bl->bl_blocks); return (filled); } else { return 0; @@ -384,9 +396,9 @@ blist_gapfind(blist_t bl, swblk_t *maxbp, swblk_t *maxep) } } - KASSERT(*maxbp <= *maxep); - KASSERT(*maxbp < bl->bl_blocks); - KASSERT(*maxep <= bl->bl_blocks); + KDASSERT(*maxbp <= *maxep); + KDASSERT(*maxbp < bl->bl_blocks); + KDASSERT(*maxep <= bl->bl_blocks); } /* @@ -638,6 +650,17 @@ blst_meta_alloc(blmeta_t *scan, swblk_t blkat, } for (i = 1; i <= skip; i += next_skip) { + if (scan[i].bm_bighint == (swblk_t)-1) { + /* + * Terminator + * + * note: check it first, as swblk_t may be unsigned. + * otherwise, the second if() might match and the + * Terminator will be ignored. + */ + break; + } + if (count <= scan[i].bm_bighint && blk + (swblk_t)radix > blkat) { /* @@ -659,11 +682,6 @@ blst_meta_alloc(blmeta_t *scan, swblk_t blkat, return(r); } /* bighint was updated by recursion */ - } else if (scan[i].bm_bighint == (swblk_t)-1) { - /* - * Terminator - */ - break; } else if (count > (swblk_t)radix) { /* * count does not fit in object even if it were @@ -1231,10 +1249,16 @@ main(int ac, char **av) if (sscanf(buf + 1, "%li %li", &count, &blkat) == 1) { printf("count %lu\n", count); swblk_t blk = blist_alloc(bl, count); - printf(" R=%04lx\n", blk); + if (blk == SWAPBLK_NONE) + printf(" R=SWAPBLK_NONE\n"); + else + printf(" R=%04lx\n", blk); } else if (sscanf(buf + 1, "%li %li", &count, &blkat) == 2) { swblk_t blk = blist_allocat(bl, count, blkat); - printf(" R=%04lx\n", blk); + if (blk == SWAPBLK_NONE) + printf(" R=SWAPBLK_NONE\n"); + else + printf(" R=%04lx\n", blk); } else { printf("?\n"); } -- 2.20.1