Bitmap in Linux

[lilzz]

Code: Select all

unsigned long *word;
*w = bitmap_weight(word, BATADV_TQ_LOCAL_WINDOW_SIZE);


/* shift the packet array by n places. */
static void batadv_bitmap_shift_left(unsigned long *seq_bits, int32_t n)
{
	if (n <= 0 || n >= BATADV_TQ_LOCAL_WINDOW_SIZE)
		return;

	bitmap_shift_left(seq_bits, seq_bits, n, BATADV_TQ_LOCAL_WINDOW_SIZE);
}


/* receive and process one packet within the sequence number window.
 *
 * returns:
 *  1 if the window was moved (either new or very old)
 *  0 if the window was not moved/shifted.
 */
int batadv_bit_get_packet(void *priv, unsigned long *seq_bits,
			  int32_t seq_num_diff, int set_mark)
{
	struct batadv_priv *bat_priv = priv;

	/* sequence number is slightly older. We already got a sequence number
	 * higher than this one, so we just mark it.
	 */
	if (seq_num_diff <= 0 && seq_num_diff > -BATADV_TQ_LOCAL_WINDOW_SIZE) {
		if (set_mark)
			batadv_set_bit(seq_bits, -seq_num_diff);
		return 0;
	}

	/* sequence number is slightly newer, so we shift the window and
	 * set the mark if required
	 */
	if (seq_num_diff > 0 && seq_num_diff < BATADV_TQ_LOCAL_WINDOW_SIZE) {
		batadv_bitmap_shift_left(seq_bits, seq_num_diff);

		if (set_mark)
			batadv_set_bit(seq_bits, 0);
		return 1;
	}

	/* sequence number is much newer, probably missed a lot of packets */
	if (seq_num_diff >= BATADV_TQ_LOCAL_WINDOW_SIZE &&
	    seq_num_diff < BATADV_EXPECTED_SEQNO_RANGE) {
		batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
			   "We missed a lot of packets (%i) !\n",
			   seq_num_diff - 1);
		bitmap_zero(seq_bits, BATADV_TQ_LOCAL_WINDOW_SIZE);
		if (set_mark)
			batadv_set_bit(seq_bits, 0);
		return 1;
	}

	/* received a much older packet. The other host either restarted
	 * or the old packet got delayed somewhere in the network. The
	 * packet should be dropped without calling this function if the
	 * seqno window is protected.
	 *
	 * seq_num_diff <= -BATADV_TQ_LOCAL_WINDOW_SIZE
	 * or
	 * seq_num_diff >= BATADV_EXPECTED_SEQNO_RANGE
	 */
	batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
		   "Other host probably restarted!\n");

	bitmap_zero(seq_bits, BATADV_TQ_LOCAL_WINDOW_SIZE);
	if (set_mark)
		batadv_set_bit(seq_bits, 0);

	return 1;
}

1)what's bitmap_weight? couldn't find a reference
2)why the need to use bitmap from above?

[PeterO]

How do you expect people to help when all you post is a random bit of source code with absolutely no context ?

PeterO

[lilzz]

How do you expect people to help when all you post is a random bit of source code with absolutely no context ?

PeterO

Care to comment on this ? Not sure what's the purpose of DECLARE_BITMAP?

Code: Select all

#define DECLARE_BITMAP(name,bits) \
unsigned long name[BITS_TO_LONGS(bits)]

#define BITS_TO_LONGS(nr)       DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long))
#define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d))
#define BITS_PER_BYTE 8

[rpdom]

Without some context, like what program is the code from, what does it do, we cannot even guess unless we are fairly familiar with those particular lines of code out of the hundreds of millions that make up the OS and applications.

[aTao]

Care to comment on this ? Not sure what's the purpose of DECLARE_BITMAP?

Code: Select all

#define DECLARE_BITMAP(name,bits) \
unsigned long name[BITS_TO_LONGS(bits)]

#define BITS_TO_LONGS(nr)       DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long))
#define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d))
#define BITS_PER_BYTE 8

What e have here is poorly commented code. The author can glean their original meaning from the names used, but to an outsider then this is reverse engineering.
However, substituting names through the defines we get:

Code: Select all

#define DECLARE_BITMAP(name,bits) unsigned long name[(((bits) + ({number of bits in long}) -1) / ({number of bits in long}))]

which, to me looks like
from name select the long that contains the bit with index bits

Well nearly...........

[PeterO]

Care to comment on this ?

Care to read this ? http://www.catb.org/esr/faqs/smart-questions.html
PeterO

[RaTTuS]

Care to comment on this ?

Care to read this ? http://www.catb.org/esr/faqs/smart-questions.html
PeterO

tldr ;-p
seriously read and understand ^

[jojopi]

Not sure what's the purpose of DECLARE_BITMAP?

Do you understand what #define does? If so, it should be pretty clear that when someone uses the DECLARE_BITMAP() macro, its expansion will be the declaration of an array variable. It literally declares a bitmap with the chosen name and size.

why the need to use bitmap from above?

A bitmap is a data structure that packs truth values into individual bits. It is slower and more complex to access than an array of integers, but uses much less memory.

Are you using layer2 batman routing, or is this just part of your patented approach of reading a random part of the Linux kernel and hoping to understand it? I think you would be better to read a book or tutorial on C, and then try writing and debugging your own programs.