Skip to contentSkip to conversation

bitmap­_find_free_region and bitmap_full arg doubts

DISCUSSION Komal Shah 3 participants 6 messages Nov 30, 2006 – Dec 1, 2006

lore
Share & tools
lore

Komal Shah

author
#0 lore raw

Hi,

I was writing the test module, for layered bitmaps, specific to my requirement such that I want to have control/track of 2GB virtual address space. As per the discussion with Paul Mundt, I have taken the approach of segmenting the virt. space with 128MB of blocks and then to do find_next_zero_bit followed by bitmap_find_free_region on the bitmaps.

I have attached the test module code. I have confusion about the what to pass as second argument of bitmap_find_free_region for 2nd layer bitmap.

Do we have to pass "total size of the block...here 128MB" as the second argument or no. of bits in that block, which 32768 (128 >> PAGE_SHIFT) ?

This confusion arised as store queue implementation (sq.c) of sh arch, passes total size of the bitmap (64M) as the second argument instead of bits.

Same is the case with bitmap_full, where I have to pass total size of the block (here 128MB) instead of no. of bits, in-order it to make my test module work correctly.

--
Link: sq.c
http://www.kernel.org/git/?p=linux/kernel/git/torvalds/linux-2.6.git;a=blob;h=7bcc73f9b8df535ad8887383aeac71a8b2491ef5;hb=0215ffb08ce99e2bb59eca114a99499a4d06e704;f=arch/sh/kernel/cpu/sh4/sq.c

Signature · 2 lines
---Komal Shah
http://komalshah.blogspot.com

/* test module for layered bitmaps */

#include <linux/init.h>
#include <linux/module.h>
#include <linux/err.h>
#include <linux/clk.h>
#include <asm/bitops.h>
#include <asm/sizes.h>

#define VIRT_SIZE SZ_2G
#define L1_BM_SEG_SIZE 0x8000000 /* 128MB */
#define L1_BM_NUM_SEGS (VIRT_SIZE / L1_BM_SEG_SIZE)
#define L1_BM_BITS L1_BM_NUM_SEGS /* 16 bits */

#define L2_BM_BITS (L1_BM_SEG_SIZE >> PAGE_SHIFT)
#define L2_BM_SIZE L1_BM_SEG_SIZE
#define L2_BM_LONGS ((L2_BM_BITS + BITS_PER_LONG - 1) / BITS_PER_LONG)

static unsigned long bm_l1 = 0x0000;
static unsigned long *bm_l2;
static unsigned long next_off = 0x0;

#define start_addr 0x80000000

static unsigned long test_find_free_region(unsigned long size)

{
	int l1_off, l2_off;
	unsigned long addr = 0x0;
	unsigned int order;
	unsigned long *tmp_bm;

	if (size > L1_BM_SEG_SIZE) {
		printk(KERN_ERR "size greater than 128MB is not allowed\n");
		return -EINVAL;
	}

	order = get_order(size);

next_block:

	l1_off = find_next_zero_bit(&bm_l1, L1_BM_BITS, next_off);
	if (l1_off >= L1_BM_BITS) {
		printk(KERN_ERR "layer1 bitmap is full\n");
		return -EINVAL;
	}

	tmp_bm = bm_l2 + (l1_off * L2_BM_LONGS);
	l2_off = bitmap_find_free_region(tmp_bm, 32768 /* L2_BM_SIZE */,
					 order);

	printk(KERN_INFO "l1_off %d l2_off %d\n", l1_off, l2_off);
	if (l2_off < 0) {
		next_off = (l1_off >= L1_BM_BITS) ? 0 : (next_off + 1);
		if (bitmap_full(tmp_bm, L2_BM_SIZE /*L2_BM_BITS*/)) {
			set_bit(l1_off, &bm_l1);
		}
		printk(KERN_INFO "go to next_block %ld\n", next_off);
		goto next_block;
	}

	if (bitmap_full(tmp_bm, L2_BM_SIZE /*L2_BM_BITS*/)) {
		set_bit(l1_off, &bm_l1);
	}

	addr = (l1_off * L1_BM_SEG_SIZE) + (l2_off << PAGE_SHIFT);

	return (addr + start_addr);
}

static int __init test_alloc_init(void)

{
	/*required ulongs for storage of nr_bits */
	unsigned int size = (L2_BM_BITS + (BITS_PER_LONG - 1)) / BITS_PER_LONG;
	unsigned long addr;

	/* sixteen 128MB layer 2 bitmaps */
	bm_l2 = kzalloc(size * L1_BM_NUM_SEGS, GFP_KERNEL);
	if (!bm_l2) {
		printk(KERN_INFO "No memory...\n");
		return -EINVAL;
	}
	addr = test_find_free_region(SZ_64M);
	printk(KERN_INFO "addr is 0x%lx\n", addr);

	addr = test_find_free_region(SZ_64M + SZ_32M);
	printk(KERN_INFO "addr is 0x%lx\n", addr);

	addr = test_find_free_region(SZ_128M);
	printk(KERN_INFO "addr is 0x%lx\n", addr);

	return 0;
}

static void __exit test_alloc_exit(void)

{
	/* TODO: care to free allocations :) */
}

module_init(test_alloc_init);
module_exit(test_alloc_exit);
MODULE_LICENSE("GPL");

#1 lore raw

M. R. Brown and Paul Mundt -- take a look at the question at end of this post.

Quoted 9 lines · Komal

I have attached the test module code. I have confusion about the what to pass as second argument of bitmap_find_free_region for 2nd layer bitmap.

Do we have to pass "total size of the block...here 128MB" as the second argument or no. of bits in that block, which 32768 (128 >> PAGE_SHIFT) ?

Quoted 7 lines

This confusion arised as store queue implementation (sq.c) of sh arch, passes total size of the bitmap (64M) as the second argument instead of bits.

Same is the case with bitmap_full, where I have to pass total size of the block (here 128MB) instead of no. of bits, in-order it to make my test module work correctly.

A bitmap is essentially an array of bits. The bitmap_* routines should take a count of how many bits are in the bitmap array (or in your case, how many bits are in the segment that you expect to be used in that call.)

So I'm guessing you will be passing L2_BM_BITS for that second argument.

The call to bitmap_find_free_region(), in arch/sh/kernel/cpu/sh4/sq.c looks bogus:

        page = bitmap_find_free_region(sq_bitmap, 0x04000000,
                                       get_order(map->size));

It says the bitmap has 0x04000000 bits. This would take 0x04000000 / 8 which is 8388608 (decimal) bytes to hold. That's an insanely huge bitmap - 8 million bytes worth of bits.

I can't make entire sense of the the code you attached. I get confused over the various sizes of maps and what the maps represent, and of bits and bytes, and of the two levels.

When you do call bitmap_find_free_region(), you should pass the number of bits that are in that segment of the L2 bitmap, which I would guess is L2_BM_BITS (32 K).

When you kzalloc() the L2 bitmap for all 16 segments at once, you should pass the number of -bytes-, not the number of longs. That is, I guess you want to replace your line:

	bm_l2 = kzalloc(size * L1_BM_NUM_SEGS, GFP_KERNEL);

with the line:

	bm_l2 = kzalloc(size * L1_BM_NUM_SEGS * sizeof(long), GFP_KERNEL);

This is because, like most of the *alloc() routines, kzalloc() takes a byte count, not a long count. The related DECLARE_BITMAP() macro computes the number of longs, not bytes, but that is because it is declaring an array of longs, not allocating a number of bytes.

But I might be entirely confused about what this code is doing.

If this code is to become a kernel patch proposal, it will take some work to make it easier to understand.

See also the code and comments in lib/bitmap.c for the routine bitmap_find_free_region() to see what it is doing.

And, as I noted above, I suspect that the arch sh code using these bitmap routines is seriously wrong, and will blow up if ever asked to handle the harder, more full, cases.

M. R. Brown and Paul Mundt - looks like you two are listed as authors for that sh arch code for "SH-4 integrated Store Queues".

Could you take a look at it, and see whether it is that code, or my brain, that is on drugs?

Signature · 3 lines
                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.925.600.0401
#2 lore raw

Re: bitmap?_find_free_region and bitmap_full arg doubts

Quoted 10 lines · Paul Jackson

The call to bitmap_find_free_region(), in arch/sh/kernel/cpu/sh4/sq.c looks bogus:

        page = bitmap_find_free_region(sq_bitmap, 0x04000000,
                                       get_order(map->size));

It says the bitmap has 0x04000000 bits. This would take 0x04000000 / 8 which is 8388608 (decimal) bytes to hold. That's an insanely huge bitmap - 8 million bytes worth of bits.

Ouch, you're right, for some reason we missed the >> PAGE_SHIFT here, even though it was handled properly in sq_api_init(). I suppose we haven't hit this in practice as most of the users end up being quite small. I'll fix it up. Good catch, thanks!

#3 lore raw

Re: bitmap?_find_free_region and bitmap_full arg doubts

Quoted 1 line · Paul Mundt

I'll fix it up. Good catch, thanks!

You're welcome.

Signature · 3 lines
                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.925.600.0401
author
#4 lore raw
In reply to Paul Jackson
Quoted 33 lines · Paul Jackson

M. R. Brown and Paul Mundt -- take a look at the question at end of this post.

Quoted 9 lines · Komal

I have attached the test module code. I have confusion about the what to pass as second argument of bitmap_find_free_region for 2nd layer bitmap.

Do we have to pass "total size of the block...here 128MB" as the second argument or no. of bits in that block, which 32768 (128 >> PAGE_SHIFT) ?

Quoted 7 lines

This confusion arised as store queue implementation (sq.c) of sh arch, passes total size of the bitmap (64M) as the second argument instead of bits.

Same is the case with bitmap_full, where I have to pass total size of the block (here 128MB) instead of no. of bits, in-order it to make my test module work correctly.

A bitmap is essentially an array of bits. The bitmap_* routines should take a count of how many bits are in the bitmap array (or in your case, how many bits are in the segment that you expect to be used in that call.)

So I'm guessing you will be passing L2_BM_BITS for that second argument.

The call to bitmap_find_free_region(), in arch/sh/kernel/cpu/sh4/sq.c looks bogus:

        page = bitmap_find_free_region(sq_bitmap, 0x04000000,
                                       get_order(map->size));
Quoted 8 lines

It says the bitmap has 0x04000000 bits. This would take 0x04000000 / 8 which is 8388608 (decimal) bytes to hold. That's an insanely huge bitmap - 8 million bytes worth of bits.

I can't make entire sense of the the code you attached. I get confused over the various sizes of maps and what the maps represent, and of bits and bytes, and of the two levels.

Thanx for clarifying. I am now able to understand it properly, and I will modify my code, so that it will be easy to understand/read :)

Signature · 2 lines
---Komal Shah
http://komalshah.blogspot.com
author
#5 lore raw
In reply to Paul Jackson
Quoted 53 lines · Paul Jackson

M. R. Brown and Paul Mundt -- take a look at the question at end of this post.

Quoted 9 lines · Komal

I have attached the test module code. I have confusion about the what to pass as second argument of bitmap_find_free_region for 2nd layer bitmap.

Do we have to pass "total size of the block...here 128MB" as the second argument or no. of bits in that block, which 32768 (128 >> PAGE_SHIFT) ?

Quoted 7 lines

This confusion arised as store queue implementation (sq.c) of sh arch, passes total size of the bitmap (64M) as the second argument instead of bits.

Same is the case with bitmap_full, where I have to pass total size of the block (here 128MB) instead of no. of bits, in-order it to make my test module work correctly.

A bitmap is essentially an array of bits. The bitmap_* routines should take a count of how many bits are in the bitmap array (or in your case, how many bits are in the segment that you expect to be used in that call.)

So I'm guessing you will be passing L2_BM_BITS for that second argument.

The call to bitmap_find_free_region(), in arch/sh/kernel/cpu/sh4/sq.c looks bogus:

        page = bitmap_find_free_region(sq_bitmap, 0x04000000,
                                       get_order(map->size));

It says the bitmap has 0x04000000 bits. This would take 0x04000000 / 8 which is 8388608 (decimal) bytes to hold. That's an insanely huge bitmap - 8 million bytes worth of bits.

I can't make entire sense of the the code you attached. I get confused over the various sizes of maps and what the maps represent, and of bits and bytes, and of the two levels.

When you do call bitmap_find_free_region(), you should pass the number of bits that are in that segment of the L2 bitmap, which I would guess is L2_BM_BITS (32 K).

When you kzalloc() the L2 bitmap for all 16 segments at once, you should pass the number of -bytes-, not the number of longs. That is, I guess you want to replace your line:

        bm_l2 = kzalloc(size * L1_BM_NUM_SEGS, GFP_KERNEL);

with the line:

Quoted 8 lines
        bm_l2 = kzalloc(size * L1_BM_NUM_SEGS * sizeof(long), GFP_KERNEL);

This is because, like most of the *alloc() routines, kzalloc() takes a byte count, not a long count. The related DECLARE_BITMAP() macro computes the number of longs, not bytes, but that is because it is declaring an array of longs, not allocating a number of bytes.

But I might be entirely confused about what this code is doing.

Oops, forgot to reply on this. This code is just a test module in-order to go for layered bitmaps and in-turn understand bitmap_* apis. As I said, requirement was to manage 2GB of virtual space of the co-processor I have attached with ARM11. Now, as we can't allocate single bitmap for 2GB, Paul Mundt suggested to have a layered bitmaps, where 1st bitmap segmenting the virtual space into 128MB blocks and have 2nd layer 128MB size bitmap for each segment in layer 1 bitmap. Hope this clarifies the motivation behind it.

Signature · 2 lines
---Komal Shah
http://komalshah.blogspot.com