I was looking at the following code recently:

static int gfs2_bitmap_create(struct gfs2_bmap *bmap, uint64_t size,
                                           uint8_t chunksize)
{
        if((((chunksize >> 1) << 1) != chunksize) && chunksize != 1)
                return -1;
        if(chunksize > 8)
                return -1;
        bmap->chunksize = chunksize;
        bmap->chunks_per_byte = 8 / chunksize;

        bmap->size = size;

        /* Have to add 1 to BITMAP_SIZE since it's 0-based and mallocs
         * must be 1-based */
        bmap->mapsize = BITMAP_SIZE(size, bmap->chunks_per_byte)+1;

        if(!(bmap->map = malloc(sizeof(char) * bmap->mapsize)))
                return -ENOMEM;
        if(!memset(bmap->map, 0, sizeof(char) * bmap->mapsize)) {
                free(bmap->map);
                bmap->map = NULL;
                return -ENOMEM;
        }

Now there are several things which immediately struck me about this bit of code. Firstly the initial test on chunksize seems to be rather long winded and it took me a while to realise that those shifts were in fact just implementing (chunksize&1). Secondly it rather looks like chunksize of anything other than a power of two would be nonsense, and that isn't tested for at all.

The comment about BITMAP_SIZE looks like total nonsense, it isn't based on anything, its just a size and the +1 is most likely due to rounding in the division which has been obscured by this pointless macro.

The thing which most amazed me though was the call to memset() and I wonder just how that is expected to fail...

Looking further through this code, there is this:

int gfs2_block_mark(struct gfs2_sbd *sdp, struct gfs2_block_list *il,
                    uint64_t block, enum gfs2_mark_block mark)
{
        int err = 0;

        if(mark == gfs2_bad_block)
                gfs2_special_set(&sdp->bad_blocks, block);
        else if(mark == gfs2_dup_block)
                gfs2_special_set(&sdp->dup_blocks, block);
        else if(mark == gfs2_eattr_block)
                gfs2_special_set(&sdp->eattr_blocks, block);
        else
                err = gfs2_bitmap_set(&il->list.gbmap.group_map, block,
                                      mark_to_gbmap[mark]);
        return err;
}

and this also worries me. Each of the calls to gfs2_special_set() hides a linear lookup over a list which presumably might become very long, so that the operation is O(n^2) wrt the list length. In addition to that, the bitmap is not a very efficient data structure in terms of memory usage, either.

I think we really need to replace this with an extent cache of some kind, where each extent can be tagged with various useful bits of information about the block type and allocation state. Such a thing would need to take the form of a tree indexed by the block number (and potentially also by the tags attached). Probably an rbtree or something along similar lines would suffice, with the important feature of keeping the data structure down to a minimum size.

Also a useful feature would be to change the "default" state so that extents not in the tree could be considered as being free (in a mostly empty filesystem) or allocated (in a mostly full filesystem).

It seems that one of the main problems with the utilities is that they rely almost totally on lists of objects, and that is the source of a lot of inefficiency.

This isn't an easy task, and it will take some thinking about to do it right, but it seems like a generally useful thing to have, and will certainly speed up a number of operations.