intmain() { unsignedint a = 0xfffffffa; unsignedint b = a + 10; unsignedint c = 4; printf("a = %u, 0x%08x\n", a, a); printf("b = %u, 0x%08x\n", b, b); printf("b - a = %u, 0x%08x\n", b - a, b - a); printf("c - a = %u, 0x%08x\n", c - a, c - a); return0; }
/* a = 4294967290, 0xfffffffa b = 4, 0x00000004 -> a + 10 = 0x1 00 00 00 04 溢出 因为 uint32 共计 32 位，溢出时的最高位无法获取，只能获取低 32 位，即 0x00000004 b - a = 10, 0x0000000a -> b - a = 4 + (-4294967290 的补码) = 0x04 + (~(0xfffffffa)+1) = 0x04 + 0x00000006 = 0x0a = 10 -> b - a = 0x04 - 0xfffffffa = -4294967286 + 2^32 = 0x0000000a = 10 因为 4 - 4294967290 将变成一个负值，这在无符号整数表示中是不允许的。 为了处理这种情况，结果会被加上一个模数（即 2^32），以得到正确的无符号结果。 c - a = 10, 0x0000000a */
Linux 内核 kfifo 环形队列
Linux 内核中有一个先进先出的数据结构，采用环形队列的数据结构来实现，提供一个无边界的字节流服务。最重要的是，这个队列采用的是无锁的方式来实现。即当它用于只有一个入队线程和一个出队线程的场景时，两个线程可以并发操作，而不需要任何加锁行为，就可以保证 kfifo 的线程安全。这个队列名为 kfifo。
数据结构
1 2 3 4 5 6 7
structkfifo { unsignedchar *buffer; /* the buffer holding the data */ unsignedint size; /* the size of the allocated buffer */ unsignedint in; /* data is added at offset (in % size) */ unsignedint out; /* data is extracted from off. (out % size) */ spinlock_t *lock; /* protects concurrent modifications */ };
/** * kfifo_alloc - allocates a new FIFO and its internal buffer * @size: the size of the internal buffer to be allocated. * @gfp_mask: get_free_pages mask, passed to kmalloc() * @lock: the lock to be used to protect the fifo buffer * * The size will be rounded-up to a power of 2. */ struct kfifo *kfifo_alloc(unsignedint size, unsignedint __nocast gfp_mask, spinlock_t *lock) { unsignedchar *buffer; structkfifo *ret;
/* * round up to the next power of 2, since our 'let the indices * wrap' tachnique works only in this case. */ if (size & (size - 1)) { // 如果不是 2 的幂次方，则向上取到 2 的幂次方 BUG_ON(size > 0x80000000); size = roundup_pow_of_two(size); }
buffer = kmalloc(size, gfp_mask); if (!buffer) return ERR_PTR(-ENOMEM);
ret = kfifo_init(buffer, size, gfp_mask, lock);
if (IS_ERR(ret)) kfree(buffer);
return ret; }
/** * kfifo_init - allocates a new FIFO using a preallocated buffer * @buffer: the preallocated buffer to be used. * @size: the size of the internal buffer, this have to be a power of 2. * @gfp_mask: get_free_pages mask, passed to kmalloc() * @lock: the lock to be used to protect the fifo buffer * * Do NOT pass the kfifo to kfifo_free() after use ! Simply free the * struct kfifo with kfree(). */ struct kfifo *kfifo_init(unsignedchar *buffer, unsignedint size, unsignedint __nocast gfp_mask, spinlock_t *lock) { structkfifo *fifo;
/* size must be a power of 2 */ BUG_ON(size & (size - 1));
fifo = kmalloc(sizeof(struct kfifo), gfp_mask); if (!fifo) return ERR_PTR(-ENOMEM);
/** * __kfifo_put - puts some data into the FIFO, no locking version * @fifo: the fifo to be used. * @buffer: the data to be added. * @len: the length of the data to be added. * * This function copies at most 'len' bytes from the 'buffer' into * the FIFO depending on the free space, and returns the number of * bytes copied. * * Note that with only one concurrent reader and one concurrent * writer, you don't need extra locking to use these functions. * 注意，对于仅一个并发的读者和写者，使用这些功能不需要额外的锁 */ unsignedint __kfifo_put(struct kfifo *fifo, unsignedchar *buffer, unsignedint len) { unsignedint l;
/* (in-out) 表示已使用的空间，size-(in-out)表示剩余的空间。通过 min 来防止写越界 */ len = min(len, fifo->size - fifo->in + fifo->out);
/* 下面的设计考虑了：从队列尾部填充一部分、从队列首部填充剩余的部分的情况 */ /* first put the data starting from fifo->in to buffer end */ /* fifo->buffer = |0........in....size-1| 首先将前半部分数据缓存放在 in~size-1 所在的区间 */ l = min(len, fifo->size - (fifo->in & (fifo->size - 1))); memcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l);
/* then put the rest (if any) at the beginning of the buffer */ /* 若 l<len，则表明上面 in~size-1 区间不够放下 len 长度，此时要将剩余后半部分数据从环的开始端继续放 */ memcpy(fifo->buffer, buffer + l, len - l);
fifo->in += len; /* 从这里可以说明，指针 in 一直在增加，其值未曾对 size 取模 */
return len; }
根据前面的《无符号整数溢出回绕》小节可知，无符号数 in 相当于 b，无符号数 out 相当于 a，当 out 很大、in 溢出回绕时，in-out(b-a) 的距离仍为正确值。无论何时，即使发生整数回绕，kfifo 中的指针都有如下关系：
/** * __kfifo_get - gets some data from the FIFO, no locking version * @fifo: the fifo to be used. * @buffer: where the data must be copied. * @len: the size of the destination buffer. * * This function copies at most 'len' bytes from the FIFO into the * 'buffer' and returns the number of copied bytes. * * Note that with only one concurrent reader and one concurrent * writer, you don't need extra locking to use these functions. * 注意，对于仅一个并发的读者和写者，使用这些功能不需要额外的锁 */ unsignedint __kfifo_get(struct kfifo *fifo, unsignedchar *buffer, unsignedint len) { unsignedint l;
/* 后面的原理跟__kfifo_put 的原理一致 */ /* first get the data from fifo->out until the end of the buffer */ l = min(len, fifo->size - (fifo->out & (fifo->size - 1))); memcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l);
/* then get the rest (if any) from the beginning of the buffer */ memcpy(buffer + l, fifo->buffer, len - l);
fifo->out += len; /* 从这里可以说明，指针 out 一直在增加，其值未曾对 size 取模 */
return len; }
__kfifio_reset 重置队列
1 2 3 4 5 6 7 8
/** * __kfifo_reset - removes the entire FIFO contents, no locking version * @fifo: the fifo to be emptied. */ staticinlinevoid __kfifo_reset(struct kfifo *fifo) { fifo->in = fifo->out = 0; }
/** * kfifo_put - puts some data into the FIFO * @fifo: the fifo to be used. * @buffer: the data to be added. * @len: the length of the data to be added. * * This function copies at most 'len' bytes from the 'buffer' into * the FIFO depending on the free space, and returns the number of * bytes copied. */ staticinlineunsignedintkfifo_put(struct kfifo *fifo, unsignedchar *buffer, unsignedint len) { unsignedlong flags; unsignedint ret;
spin_lock_irqsave(fifo->lock, flags); ret = __kfifo_put(fifo, buffer, len); spin_unlock_irqrestore(fifo->lock, flags);
return ret; }
/** * kfifo_get - gets some data from the FIFO * @fifo: the fifo to be used. * @buffer: where the data must be copied. * @len: the size of the destination buffer. * * This function copies at most 'len' bytes from the FIFO into the * 'buffer' and returns the number of copied bytes. */ staticinlineunsignedintkfifo_get(struct kfifo *fifo, unsignedchar *buffer, unsignedint len) { unsignedlong flags; unsignedint ret;
spin_lock_irqsave(fifo->lock, flags); ret = __kfifo_get(fifo, buffer, len);
/* * optimization: if the FIFO is empty, set the indices to 0 * so we don't wrap the next time */ if (fifo->in == fifo->out) fifo->in = fifo->out = 0; spin_unlock_irqrestore(fifo->lock, flags);
