[ltt-dev] [RFC] Portable bitfield library for trace format (v2)
Mathieu Desnoyers
mathieu.desnoyers at efficios.com
Mon Sep 20 00:29:07 EDT 2010
I'm keeping the same introduction as (v1), but I'm appending v2 of my portable
bitfield library below. Comments are welcome,
Changelog since v1:
* Add missing brackets around "ptr" in the macros.
* Add more tests, including tests using randomly generated input values.
Thanks,
Mathieu
* Mathieu Desnoyers (mathieu.desnoyers at efficios.com) wrote:
> Hi,
>
> After looking at gcc bitfields, I found out that they were really non-portable.
> One particularity of these bitfields is that the fields are put from high to low
> bits on big endian, and from low to high bits on little endian. So it is not
> enough to do the byte swap between architectures, one must also take care to
> reorder the fields.
>
> Also, the fact that gcc requires bitfields to fit in the current unit adds much
> padding that is unwanted in a trace e.g.
>
> struct {
> int a:3;
> int b:31;
> int c:3;
> };
>
> will be 12 bytes in size because "b" does not fit in the first "int" unit.
>
> So I created a bitfield library with write and read primitives that can be made
> compatible with gcc bitfields by specifying the bit padding manually. The
> write-side writes bitfields in the native endianness, either with 1, 2, 4 or 8
> bytes memory writes. The read side is architecture-agnostic, so it can read
> bitfields generated by either little or big endian architectures.
>
> The userspace code is below. It includes a rather useful test-suite. The code
> generated is quite compact when the parameters are fixed. A x86-32 disassembly
> of fct() below which contains the macro instance:
>
> unsigned int glob[1];
>
> void fct(void)
> {
> bitfield_write(glob, 0x12345678, 12, 15);
> }
>
> Compared to this, we have the generated assembly from gcc 4.3.4 for:
>
> struct d3 {
> unsigned int a:12;
> unsigned int b:15;
> };
>
> struct d3 glob;
>
> void fct(void)
> {
> glob.b = 0x12345678;
> }
>
> glob.b = 0x12345678;
>
> On x86-32, the bitfield library looks like:
>
> 08048470 <fct>:
> 8048470: a1 70 ba 04 08 mov 0x804ba70,%eax
> 8048475: 55 push %ebp
> 8048476: 89 e5 mov %esp,%ebp
> 8048478: 5d pop %ebp
> 8048479: 25 ff 0f 00 f8 and $0xf8000fff,%eax
> 804847e: 0d 00 80 67 05 or $0x5678000,%eax
> 8048483: a3 70 ba 04 08 mov %eax,0x804ba70
> 8048488: c3 ret
> 8048489: 8d b4 26 00 00 00 00 lea 0x0(%esi,%eiz,1),%esi
>
> The gcc bitfields generate:
>
> 080483d0 <fct>:
> 80483d0: a1 64 96 04 08 mov 0x8049664,%eax
> 80483d5: 55 push %ebp
> 80483d6: 89 e5 mov %esp,%ebp
> 80483d8: 5d pop %ebp
> 80483d9: 25 ff 0f 00 f8 and $0xf8000fff,%eax
> 80483de: 0d 00 80 67 05 or $0x5678000,%eax
> 80483e3: a3 64 96 04 08 mov %eax,0x8049664
> 80483e8: c3 ret
> 80483e9: 8d b4 26 00 00 00 00 lea 0x0(%esi,%eiz,1),%esi
>
>
> and on powerpc 32, the bitfield library:
>
> 10000520 <fct>:
> 10000520: 3d 20 10 01 lis r9,4097
> 10000524: 80 09 33 80 lwz r0,13184(r9)
> 10000528: 54 00 06 d6 rlwinm r0,r0,0,27,11
> 1000052c: 64 00 00 0a oris r0,r0,10
> 10000530: 60 00 cf 00 ori r0,r0,52992
> 10000534: 90 09 33 80 stw r0,13184(r9)
> 10000538: 4e 80 00 20 blr
> 1000053c: 60 00 00 00 nop
>
> And gcc bitfields:
>
> 10000490 <fct>:
> 10000490: 3d 20 10 01 lis r9,4097
> 10000494: 39 60 56 78 li r11,22136
> 10000498: 80 09 0a a4 lwz r0,2724(r9)
> 1000049c: 51 60 2b 34 rlwimi r0,r11,5,12,26
> 100004a0: 90 09 0a a4 stw r0,2724(r9)
> 100004a4: 4e 80 00 20 blr
> 100004a8: 60 00 00 00 nop
> 100004ac: 60 00 00 00 nop
>
>
> Comments are welcome (code below).
>
> Thanks,
>
> Mathieu
>
/*
* Common Trace Format
*
* Bitfields implementation
*
* Copyright 2010 - Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
*
* Dual LGPL v2.1/GPL v2 license.
*/
#include <endian.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <assert.h>
#include <time.h>
#include <strings.h>
/* We can't shift a int from 32 bit, >> 32 on int is a no-op on x86 */
#define piecewise_rshift(v, shift) \
do { \
int sb = (shift) / (sizeof(v) * 8 - 1); \
int final = (shift) % (sizeof(v) * 8 - 1); \
\
for (; sb; sb--) \
(v) >>= sizeof(v) * 8 - 1; \
(v) >>= final; \
} while (0)
/*
* Save integer to the bitfield, which starts at the "start" bit, has "len"
* bits.
* The inside of a bitfield is from high bits to low bits.
* Uses native endianness.
* For unsigned "v", pad MSB with 0 if bitfield is larger than v.
* For signed "v", sign-extend v if bitfield is larger than v.
*
* On little endian, bytes are placed from the less significant to the most
* significant. Also, consecutive bitfields are placed from lower bits to higher
* bits.
*
* On big endian, bytes are places from most significant to less significant.
* Also, consecutive bitfields are placed from higher to lower bits.
*/
#if (BYTE_ORDER == LITTLE_ENDIAN)
#define bitfield_write(ptr, _v, _start, _length) \
do { \
typeof(*(ptr)) mask, cmask; \
unsigned int start = (_start), length = (_length); \
typeof(_v) v = (_v); \
int start_unit, end_unit, this_unit; \
unsigned int end, cshift; /* cshift is "complement shift" */ \
unsigned int ts = sizeof(__typeof__(*(ptr))) * 8; /* type size */ \
\
if (!length) \
break; \
\
end = start + length; \
start_unit = start / ts; \
end_unit = (end + (ts - 1)) / ts; \
\
/* Trim v high bits */ \
if (length < sizeof(v) * 8) \
v &= ~(~0ULL << length); \
\
/* We can now append v with a simple "or", shift it piece-wise */ \
this_unit = start_unit; \
if (start_unit == end_unit - 1) { \
mask = ~((typeof(*(ptr))) ~0ULL << (start % ts)); \
mask |= (typeof(*(ptr))) ~0ULL << (end % ts ? : ts); \
cmask = (typeof(*(ptr))) v << (start % ts); \
(ptr)[this_unit] &= mask; \
(ptr)[this_unit] |= cmask; \
break; \
} \
if (start % ts) { \
cshift = start % ts; \
mask = ~((typeof(*(ptr))) ~0ULL << cshift); \
cmask = (typeof(*(ptr))) v << cshift; \
(ptr)[this_unit] &= mask; \
(ptr)[this_unit] |= cmask; \
if (ts - cshift >= sizeof(v) * 8) \
piecewise_rshift(v, ts - cshift); \
else \
v >>= ts - cshift; \
start += ts - cshift; \
this_unit++; \
} \
for (; this_unit < end_unit - 1; this_unit++) { \
(ptr)[this_unit] = (typeof(*(ptr))) v; \
if (ts >= sizeof(v) * 8) \
piecewise_rshift(v, ts); \
else \
v >>= ts; \
start += ts; \
} \
if (end % ts) { \
mask = (typeof(*(ptr))) ~0ULL << (end % ts); \
cmask = (typeof(*(ptr))) v; \
(ptr)[this_unit] &= mask; \
(ptr)[this_unit] |= cmask; \
} else \
(ptr)[this_unit] = (typeof(*(ptr))) v; \
} while (0)
#else /* (BYTE_ORDER != LITTLE_ENDIAN) */
#define bitfield_write(ptr, _v, _start, _length) \
do { \
typeof(_v) v = (_v); \
unsigned int start = _start, length = _length; \
int start_unit, end_unit, this_unit; \
unsigned int end, cshift; /* cshift is "complement shift" */ \
typeof(*(ptr)) mask, cmask; \
unsigned int ts = sizeof(__typeof__(*(ptr))) * 8; /* type size */ \
\
if (!length) \
break; \
\
end = start + length; \
start_unit = start / ts; \
end_unit = (end + (ts - 1)) / ts; \
\
/* Trim v high bits */ \
if (length < sizeof(v) * 8) \
v &= ~(~0ULL << length); \
\
/* We can now append v with a simple "or", shift it piece-wise */ \
this_unit = end_unit - 1; \
if (start_unit == end_unit - 1) { \
mask = ~((typeof(*(ptr))) ~0ULL << ((ts - (end % ts)) % ts)); \
mask |= (typeof(*(ptr))) ~0ULL << (ts - (start % ts)); \
cmask = (typeof(*(ptr))) v << ((ts - (end % ts)) % ts); \
(ptr)[this_unit] &= mask; \
(ptr)[this_unit] |= cmask; \
break; \
} \
if (end % ts) { \
cshift = end % ts; \
mask = ~((typeof(*(ptr))) ~0ULL << (ts - cshift)); \
cmask = (typeof(*(ptr))) v << (ts - cshift); \
(ptr)[this_unit] &= mask; \
(ptr)[this_unit] |= cmask; \
if (cshift >= sizeof(v) * 8) \
piecewise_rshift(v, cshift); \
else \
v >>= cshift; \
end -= cshift; \
this_unit--; \
} \
for (; this_unit >= start_unit + 1; this_unit--) { \
(ptr)[this_unit] = (typeof(*(ptr))) v; \
if (ts >= sizeof(v) * 8) \
piecewise_rshift(v, ts); \
else \
v >>= ts; \
end -= ts; \
} \
if (start % ts) { \
mask = (typeof(*(ptr))) ~0ULL << (ts - (start % ts)); \
cmask = (typeof(*(ptr))) v; \
(ptr)[this_unit] &= mask; \
(ptr)[this_unit] |= cmask; \
} else \
(ptr)[this_unit] = (typeof(*(ptr))) v; \
} while (0)
#endif
/*
* Read a bitfield byte-wise. This function is arch-agnostic.
*/
uint64_t bitfield_read_64(unsigned char *ptr,
unsigned int start, unsigned int len,
int byte_order, int signedness)
{
int start_unit, end_unit, this_unit;
unsigned int end, cshift; /* cshift is "complement shift" */
unsigned int ts = sizeof(unsigned char) * 8;
unsigned char mask, cmask;
uint64_t v = 0;
if (!len)
return 0;
end = start + len;
start_unit = start / ts;
end_unit = (end + (ts - 1)) / ts;
/*
* We can now fill v piece-wise, from lower bits to upper bits.
* We read the bitfield in the opposite direction it was written.
*/
switch (byte_order) {
case LITTLE_ENDIAN:
this_unit = end_unit - 1;
if (signedness) {
if (ptr[this_unit] & (1U << ((end % ts ? : ts) - 1)))
v = ~0ULL;
}
if (start_unit == end_unit - 1) {
mask = (unsigned char) ~0ULL << (end % ts ? : ts);
mask |= ~((unsigned char) ~0ULL << (start % ts));
cmask = ptr[this_unit];
cmask &= ~mask;
cmask >>= (start % ts);
v <<= end - start;
v |= cmask;
break;
}
if (end % ts) {
cshift = (end % ts ? : ts);
mask = (unsigned char) ~0ULL << cshift;
cmask = ptr[this_unit];
cmask &= ~mask;
v <<= cshift;
v |= (uint64_t) cmask;
end -= cshift;
this_unit--;
}
for (; this_unit >= start_unit + 1; this_unit--) {
v <<= ts;
v |= (uint64_t) ptr[this_unit];
end -= ts;
}
if (start % ts) {
cmask = ptr[this_unit] >> (start % ts);
v <<= ts - (start % ts);
v |= (uint64_t) cmask;
} else {
v <<= ts;
v |= (uint64_t) ptr[this_unit];
}
break;
case BIG_ENDIAN:
this_unit = start_unit;
if (signedness) {
if (ptr[this_unit] & (1U << (ts - (start % ts) - 1)))
v = ~0ULL;
}
if (start_unit == end_unit - 1) {
mask = (unsigned char) ~0ULL << (ts - (start % ts));
mask |= ~((unsigned char) ~0ULL << ((ts - (end % ts)) % ts));
cmask = ptr[this_unit];
cmask &= ~mask;
cmask >>= (ts - (end % ts)) % ts;
v <<= end - start;
v |= (uint64_t) cmask;
break;
}
if (start % ts) {
mask = (unsigned char) ~0ULL << (ts - (start % ts));
cmask = ptr[this_unit];
cmask &= ~mask;
v <<= ts - (start % ts);
v |= (uint64_t) cmask;
start += ts - (start % ts);
this_unit++;
}
for (; this_unit < end_unit - 1; this_unit++) {
v <<= ts;
v |= (uint64_t) ptr[this_unit];
start += ts;
}
if (end % ts) {
cmask = ptr[this_unit];
cmask >>= (ts - (end % ts)) % ts;
v <<= (end % ts);
v |= (uint64_t) cmask;
} else {
v <<= ts;
v |= (uint64_t) ptr[this_unit];
}
break;
default:
assert(0);
}
return v;
}
/*
* The code below is for testing the bitfield write/read functions.
*/
unsigned int glob;
/*
* This function is only declared to show the size of a bitfield write in
* objdump.
*/
void fct(void)
{
bitfield_write(&glob, 0x12345678, 12, 15);
}
/* Test array size, in bytes */
#define TEST_LEN 128
#define NR_TESTS 10
unsigned int srcrand;
#if defined(__i386) || defined(__x86_64)
static inline int fls(int x)
{
int r;
asm("bsrl %1,%0\n\t"
"cmovzl %2,%0"
: "=&r" (r) : "rm" (x), "rm" (-1));
return r + 1;
}
#elif defined(__PPC__)
static __inline__ int fls(unsigned int x)
{
int lz;
asm ("cntlzw %0,%1" : "=r" (lz) : "r" (x));
return 32 - lz;
}
#else
static int fls(unsigned int x)
{
int r = 32;
if (!x)
return 0;
if (!(x & 0xFFFF0000U)) {
x <<= 16;
r -= 16;
}
if (!(x & 0xFF000000U)) {
x <<= 8;
r -= 8;
}
if (!(x & 0xF0000000U)) {
x <<= 4;
r -= 4;
}
if (!(x & 0xC0000000U)) {
x <<= 2;
r -= 2;
}
if (!(x & 0x80000000U)) {
x <<= 1;
r -= 1;
}
return r;
}
#endif
static void print_byte_array(const unsigned char *c, unsigned long len)
{
unsigned long i;
for (i = 0; i < len; i++) {
printf("0x%X", c[i]);
if (i != len - 1)
printf(" ");
}
printf("\n");
}
static void init_byte_array(unsigned char *c,
unsigned long len,
unsigned char val)
{
unsigned long i;
for (i = 0; i < len; i++)
c[i] = val;
}
int run_test_unsigned(void)
{
unsigned int src, nrbits;
union {
unsigned char c[TEST_LEN];
unsigned short s[TEST_LEN/2];
unsigned int i[TEST_LEN/4];
unsigned long l[TEST_LEN/4];
unsigned long long ll[TEST_LEN/2];
} target;
uint64_t readval;
unsigned int s, l;
int err = 0;
printf("Running unsigned test with 0x%X\n", srcrand);
src = srcrand;
nrbits = fls(src);
for (s = 0; s < 8 * TEST_LEN; s++) {
for (l = nrbits; l < (8 * TEST_LEN) - s; l++) {
init_byte_array(target.c, TEST_LEN, 0xFF);
bitfield_write(target.c, src, s, l);
readval = bitfield_read_64(target.c, s, l, BYTE_ORDER, 0);
if (readval != src) {
printf("Error (bytewise) src %lX read %llX shift %d len %d\n",
src, readval, s, l);
print_byte_array(target.c, TEST_LEN);
err = 1;
}
init_byte_array(target.c, TEST_LEN, 0xFF);
bitfield_write(target.s, src, s, l);
readval = bitfield_read_64(target.c, s, l, BYTE_ORDER, 0);
if (readval != src) {
printf("Error (shortwise) src %lX read %llX shift %d len %d\n",
src, readval, s, l);
print_byte_array(target.c, TEST_LEN);
err = 1;
}
init_byte_array(target.c, TEST_LEN, 0xFF);
bitfield_write(target.i, src, s, l);
readval = bitfield_read_64(target.c, s, l, BYTE_ORDER, 0);
if (readval != src) {
printf("Error (intwise) src %lX read %llX shift %d len %d\n",
src, readval, s, l);
print_byte_array(target.c, TEST_LEN);
err = 1;
}
init_byte_array(target.c, TEST_LEN, 0xFF);
bitfield_write(target.l, src, s, l);
readval = bitfield_read_64(target.c, s, l, BYTE_ORDER, 0);
if (readval != src) {
printf("Error (longwise) src %lX read %llX shift %d len %d\n",
src, readval, s, l);
print_byte_array(target.c, TEST_LEN);
err = 1;
}
init_byte_array(target.c, TEST_LEN, 0xFF);
bitfield_write(target.ll, src, s, l);
readval = bitfield_read_64(target.c, s, l, BYTE_ORDER, 0);
if (readval != src) {
printf("Error (longlongwise) src %lX read %llX shift %d len %d\n",
src, readval, s, l);
print_byte_array(target.c, TEST_LEN);
err = 1;
}
}
}
if (!err)
printf("Success!\n");
else
printf("Failed!\n");
return err;
}
int run_test_signed(void)
{
int src, nrbits;
union {
char c[TEST_LEN];
short s[TEST_LEN/2];
int i[TEST_LEN/4];
long l[TEST_LEN/4];
long long ll[TEST_LEN/8];
} target;
int64_t readval;
unsigned int s, l;
int err = 0;
printf("Running signed test with 0x%X\n", srcrand);
src = srcrand;
if (src & 0x80000000U)
nrbits = fls(~src) + 1; /* Find least significant bit conveying sign */
else
nrbits = fls(src) + 1; /* Keep sign at 0 */
for (s = 0; s < 8 * TEST_LEN; s++) {
for (l = nrbits; l < (8 * TEST_LEN) - s; l++) {
init_byte_array(target.c, TEST_LEN, 0x0);
bitfield_write(target.c, src, s, l);
readval = bitfield_read_64(target.c, s, l, BYTE_ORDER, 1);
if (readval != src) {
printf("Error (bytewise) src %lX read %llX shift %d len %d\n",
src, readval, s, l);
print_byte_array(target.c, TEST_LEN);
err = 1;
}
init_byte_array(target.c, TEST_LEN, 0x0);
bitfield_write(target.s, src, s, l);
readval = bitfield_read_64(target.c, s, l, BYTE_ORDER, 1);
if (readval != src) {
printf("Error (shortwise) src %lX read %llX shift %d len %d\n",
src, readval, s, l);
print_byte_array(target.c, TEST_LEN);
err = 1;
}
init_byte_array(target.c, TEST_LEN, 0x0);
bitfield_write(target.i, src, s, l);
readval = bitfield_read_64(target.c, s, l, BYTE_ORDER, 1);
if (readval != src) {
printf("Error (intwise) src %lX read %llX shift %d len %d\n",
src, readval, s, l);
print_byte_array(target.c, TEST_LEN);
err = 1;
}
init_byte_array(target.c, TEST_LEN, 0x0);
bitfield_write(target.l, src, s, l);
readval = bitfield_read_64(target.c, s, l, BYTE_ORDER, 1);
if (readval != src) {
printf("Error (longwise) src %lX read %llX shift %d len %d\n",
src, readval, s, l);
print_byte_array(target.c, TEST_LEN);
err = 1;
}
init_byte_array(target.c, TEST_LEN, 0x0);
bitfield_write(target.ll, src, s, l);
readval = bitfield_read_64(target.c, s, l, BYTE_ORDER, 1);
if (readval != src) {
printf("Error (longlongwise) src %lX read %llX shift %d len %d\n",
src, readval, s, l);
print_byte_array(target.c, TEST_LEN);
err = 1;
}
}
}
if (!err)
printf("Success!\n");
else
printf("Failed!\n");
return err;
}
int run_test(void)
{
int err = 0;
int i;
srand(time(NULL));
srcrand = 0;
err |= run_test_unsigned();
srcrand = 0;
err |= run_test_signed();
srcrand = 1;
err |= run_test_unsigned();
srcrand = ~0U;
err |= run_test_unsigned();
srcrand = -1;
err |= run_test_signed();
srcrand = (int)0x80000000U;
err |= run_test_signed();
for (i = 0; i < NR_TESTS; i++) {
srcrand = rand();
err |= run_test_unsigned();
err |= run_test_signed();
}
return err;
}
int main(int argc, char **argv)
{
unsigned long src;
unsigned int shift, len;
int ret;
union {
unsigned char c[8];
unsigned short s[4];
unsigned int i[2];
unsigned long l[2];
unsigned long long ll[1];
} target;
uint64_t readval;
if (argc > 1)
src = atoi(argv[1]);
else
src = 0x12345678;
if (argc > 2)
shift = atoi(argv[2]);
else
shift = 12;
if (argc > 3)
len = atoi(argv[3]);
else
len = 40;
target.i[0] = 0xFFFFFFFF;
target.i[1] = 0xFFFFFFFF;
bitfield_write(target.c, src, shift, len);
printf("bytewise\n");
print_byte_array(target.c, 8);
target.i[0] = 0xFFFFFFFF;
target.i[1] = 0xFFFFFFFF;
bitfield_write(target.s, src, shift, len);
printf("shortwise\n");
print_byte_array(target.c, 8);
target.i[0] = 0xFFFFFFFF;
target.i[1] = 0xFFFFFFFF;
bitfield_write(target.i, src, shift, len);
printf("intwise\n");
print_byte_array(target.c, 8);
target.i[0] = 0xFFFFFFFF;
target.i[1] = 0xFFFFFFFF;
bitfield_write(target.l, src, shift, len);
printf("longwise\n");
print_byte_array(target.c, 8);
target.i[0] = 0xFFFFFFFF;
target.i[1] = 0xFFFFFFFF;
bitfield_write(target.ll, src, shift, len);
printf("lluwise\n");
print_byte_array(target.c, 8);
readval = bitfield_read_64(target.c, shift, len, BYTE_ORDER, 0);
printf("read: %llX\n", readval);
ret = run_test();
return ret;
}
--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
More information about the lttng-dev
mailing list