Messages in this thread Patch in this message | | | Date | Tue, 11 Jul 2023 12:20:24 -0700 | From | Yury Norov <> | Subject | Re: [Resend v1 1/5] linux/bitqueue.h: add the bit queue implementation |
| |
+ Andy and Rasmus
On Tue, Jul 11, 2023 at 04:42:29PM +0200, Alexander Potapenko wrote: > struct bitq represents a bit queue with external storage. > > Its purpose is to easily pack sub-byte values, which can be used, for > example, to implement RLE algorithms.
Whatever it is, it's not a queue. The queue implies O(1) for insertion and deletion, but your 'dequeue' is clearly an O(n) procedure.
I'm not sure if I completely understand the purpose of the series, but from this description: enqueueing/dequeueing of sub-byte values
I think, the simplest solution would be a circular queue (ringbuffer) based on bitmaps:
Init an empty 10-bit bitmap:
Head = 0 v ..... ..... ^ Tail = 1
Enqueue 6-bit value 0b101010 at the end:
Head = 0 v 10101 0.... ^ Tail = 1
Dequeue 3 bits from the beginning:
Head = 0 v ...01 0.... ^ Tail = 1
And so on...
See some other comments inline.
Thanks, Yury
> Signed-off-by: Alexander Potapenko <glider@google.com> > --- > include/linux/bitqueue.h | 144 +++++++++++++++++++++++++++++++++++++++ > 1 file changed, 144 insertions(+) > create mode 100644 include/linux/bitqueue.h > > diff --git a/include/linux/bitqueue.h b/include/linux/bitqueue.h > new file mode 100644 > index 0000000000000..c4393f703c697 > --- /dev/null > +++ b/include/linux/bitqueue.h > @@ -0,0 +1,144 @@ > +/* SPDX-License-Identifier: GPL-2.0 */ > +/* > + * A simple bit queue which supports enqueueing/dequeueing of sub-byte values. > + * > + * This can be used to pack complex bitfields into byte arrays. > + */ > +#ifndef _LINUX_BITQUEUE_H > +#define _LINUX_BITQUEUE_H > + > +#include <linux/string.h> > +#include <linux/types.h> > + > +/** > + * struct bitq - represents a bit queue with external storage. > + * @data: data buffer used by the queue. > + * @size: size of @data in bytes. > + * @bit_pos: current bit position. > + */ > +struct bitq { > + u8 *data; > + int size, bit_pos; > +}; > + > +/** > + * bitq_init - initialize an empty bit queue. > + * @q: struct bitq to be initialized. > + * @data: external data buffer to use. > + * @size: capacity in bytes. > + * > + * Return: 0 in the case of success, -1 if either of the pointers is NULL. ENIVAL?
> + */ > +static inline int bitq_init(struct bitq *q, u8 *data, int size) > +{ > + if (!q || !data) > + return -1;
This is a useless check. Erroneous code may (and often does) pass a broken pointer other than NULL.
And to make it worse, this error handling (instead of run-time segfault which can be easily caught at debugging) may make users think that passing NULL is the right thing. Check bit/bitmap and other kernel functions: they don't check against NULL as a general rule, except for well-justified cases, like 'free(NULL)'.
> + q->data = data; > + q->size = size; > + memset(data, 0, size);
Useless memset?
> + q->bit_pos = 0; > + return 0; > +} > + > +/** > + * bitq_init_full - make a bit queue from an initialized byte array. > + * @q: struct bitq to be initialized. > + * @data: external data buffer to use. > + * @size: capacity in bytes. > + * > + * Return: 0 in the case of success, -1 if either of the pointers is NULL. > + */ > +static inline int bitq_init_full(struct bitq *q, u8 *data, int size) > +{ > + if (!q || !data) > + return -1; > + q->data = data; > + q->size = size; > + q->bit_pos = q->size * 8; > + return 0; > +}
This all should not reside in a header.
> + > +/** > + * bitq_enqueue - push up to 8 bits to the end of the queue. > + * @q: struct bitq. > + * @value: byte containing the value to be pushed. > + * @bits: number of bits (1 to 8) to push. > + * > + * Return: number of bits pushed, or -1 in the case of an error. > + */ > +static inline int bitq_enqueue(struct bitq *q, u8 value, int bits) > +{ > + int byte_pos, left_in_byte, max_pos; > + u8 hi, lo; > + > + if (!q || (bits < 1) || (bits > 8)) > + return -1;
Pushing 0 elements in queue is usually not an error. Implementations usually return and do nothing. From the malloc() man page:
If size is 0, then malloc() returns a unique pointer value that can later be successfully passed to free().
> + max_pos = q->size * 8; > + if ((max_pos - q->bit_pos) < bits) > + return -1;
ENOMEM? Or probably better to resize the queue.
> + > + left_in_byte = 8 - (q->bit_pos % 8); > + byte_pos = q->bit_pos / 8; > + /* Clamp @value. */ > + value %= (1 << bits); > + if (left_in_byte >= bits) { > + /* @value fits into the current byte. */ > + value <<= (left_in_byte - bits); > + q->data[byte_pos] |= value; > + } else { > + /* > + * @value needs to be split between the current and the > + * following bytes. > + */ > + hi = value >> (bits - left_in_byte); > + q->data[byte_pos] |= hi; > + byte_pos++; > + lo = value << (8 - (bits - left_in_byte)); > + q->data[byte_pos] |= lo; > + }
This piece should be a bitmap_append() function, like: bitmap_append(addr, 3, 2, 0b11) would append 0b11 to the bitmap at offset 3. We already have bitmap_{set,get}_value8, so I suggest to extend the interface for unaligned offsets and lengths up to BITS_PER_LONG. > + q->bit_pos += bits; > + return bits; > +} > + > +/** > + * bitq_dequeue - pop up to 8 bits from the beginning of the queue. > + * @q: struct bitq. > + * @value: u8* to store the popped value (can be NULL). > + * @bits: number of bits (1 to 8) to pop. > + * > + * Return: number of bits popped, or -1 in the case of an error. > + */ > + > +#include <linux/printk.h> > +static inline int bitq_dequeue(struct bitq *q, u8 *value, int bits) > +{ > + int rem_bits = 8 - bits, i; > + u8 output; > + > + /* Invalid arguments. */ > + if (!q || (bits < 1) || (bits > 8)) > + return -1; > + /* Not enough space to insert @bits. */ > + if (q->bit_pos < bits) > + return -1; > + /* Take the first @bits bits from the first byte. */ > + output = q->data[0]; > + output >>= rem_bits; > + if (value) > + *value = output; > + > + /* > + * Shift every byte in the queue to the left by @bits, carrying over to > + * the previous byte. > + */ > + for (i = 0; i < q->size - 1; i++) { > + q->data[i] = (q->data[i] << bits) | > + (q->data[i + 1] >> rem_bits); > + }
As I already mentioned, this is O(N), which is wrong for queues. Add a pointer to the head in the bitq structure to avoid shifting every byte.
BTW, we've got bitmap_shift_{left,right} for this. > + q->data[q->size - 1] <<= bits; > + q->bit_pos -= bits; > + return bits; > +} > + > +#endif // _LINUX_BITQUEUE_H > -- > 2.41.0.255.g8b1d071c50-goog
| |