| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <20100918054229.GA5448@Krystal>
Date: Sat, 18 Sep 2010 01:42:29 -0400
From: Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
To: ltt-dev@...ts.casi.polymtl.ca, linux-kernel@...r.kernel.org
Cc: Tasneem Brutch - SISA <t.brutch@...a.samsung.com>,
k.stewart@...escale.com, tibbitts@...ibm.com,
cristiano.l.pereira@...el.com, janghaeng.lee@....com,
jay.sim@....com, cheoljoo.lee@....com, RVGG20@...escale.com,
John.Bromhead@....com, kbarde@...wei.com,
Felix.Burton@...driver.com, sumit@...cinc.com,
"Spear, Aaron" <aaron_spear@...tor.com>,
Steven Rostedt <rostedt@...dmis.org>
Subject: [RFC] Portable bitfields for trace format
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@...icios.com>
*
* Dual LGPL v2.1/GPL v2 license.
*/
#include <endian.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <assert.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;
}
unsigned int glob[1];
void fct(void)
{
bitfield_write(glob, 0x12345678, 12, 15);
}
int run_test_unsigned(void)
{
unsigned long src;
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;
unsigned int s, l;
int err = 0;
printf("Running unsigned test\n");
src = 1;
for (s = 0; s < 64; s++) {
for (l = 1; l < 64 - s; l++) {
target.i[0] = 0xFFFFFFFF;
target.i[1] = 0xFFFFFFFF;
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);
printf("0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X\n",
target.c[0], target.c[1], target.c[2], target.c[3],
target.c[4], target.c[5], target.c[6], target.c[7]);
err = 1;
}
target.i[0] = 0xFFFFFFFF;
target.i[1] = 0xFFFFFFFF;
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);
printf("0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X\n",
target.c[0], target.c[1], target.c[2], target.c[3],
target.c[4], target.c[5], target.c[6], target.c[7]);
err = 1;
}
target.i[0] = 0xFFFFFFFF;
target.i[1] = 0xFFFFFFFF;
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);
printf("0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X\n",
target.c[0], target.c[1], target.c[2], target.c[3],
target.c[4], target.c[5], target.c[6], target.c[7]);
err = 1;
}
target.i[0] = 0xFFFFFFFF;
target.i[1] = 0xFFFFFFFF;
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);
printf("0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X\n",
target.c[0], target.c[1], target.c[2], target.c[3],
target.c[4], target.c[5], target.c[6], target.c[7]);
err = 1;
}
target.i[0] = 0xFFFFFFFF;
target.i[1] = 0xFFFFFFFF;
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);
printf("0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X\n",
target.c[0], target.c[1], target.c[2], target.c[3],
target.c[4], target.c[5], target.c[6], target.c[7]);
err = 1;
}
}
}
if (!err)
printf("Success!\n");
else
printf("Failed!\n");
return err;
}
int run_test_signed(void)
{
long src;
union {
char c[8];
short s[4];
int i[2];
long l[2];
long long ll[1];
} target;
int64_t readval;
unsigned int s, l;
int err = 0;
printf("Running signed test\n");
src = 1;
for (s = 0; s < 64; s++) {
for (l = 1; l < 64 - s; l++) {
target.i[0] = 0x00000000;
target.i[1] = 0x00000000;
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);
printf("0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X\n",
target.c[0], target.c[1], target.c[2], target.c[3],
target.c[4], target.c[5], target.c[6], target.c[7]);
err = 1;
}
target.i[0] = 0x00000000;
target.i[1] = 0x00000000;
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);
printf("0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X\n",
target.c[0], target.c[1], target.c[2], target.c[3],
target.c[4], target.c[5], target.c[6], target.c[7]);
err = 1;
}
target.i[0] = 0x00000000;
target.i[1] = 0x00000000;
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);
printf("0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X\n",
target.c[0], target.c[1], target.c[2], target.c[3],
target.c[4], target.c[5], target.c[6], target.c[7]);
err = 1;
}
target.i[0] = 0x00000000;
target.i[1] = 0x00000000;
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);
printf("0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X\n",
target.c[0], target.c[1], target.c[2], target.c[3],
target.c[4], target.c[5], target.c[6], target.c[7]);
err = 1;
}
target.i[0] = 0x00000000;
target.i[1] = 0x00000000;
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);
printf("0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X\n",
target.c[0], target.c[1], target.c[2], target.c[3],
target.c[4], target.c[5], target.c[6], target.c[7]);
err = 1;
}
}
}
if (!err)
printf("Success!\n");
else
printf("Failed!\n");
return err;
}
int run_test(void)
{
int err = 0;
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");
printf("0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X\n",
target.c[0], target.c[1], target.c[2], target.c[3],
target.c[4], target.c[5], target.c[6], target.c[7]);
target.i[0] = 0xFFFFFFFF;
target.i[1] = 0xFFFFFFFF;
bitfield_write(target.s, src, shift, len);
printf("shortwise\n");
printf("0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X\n",
target.c[0], target.c[1], target.c[2], target.c[3],
target.c[4], target.c[5], target.c[6], target.c[7]);
target.i[0] = 0xFFFFFFFF;
target.i[1] = 0xFFFFFFFF;
bitfield_write(target.i, src, shift, len);
printf("intwise\n");
printf("0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X\n",
target.c[0], target.c[1], target.c[2], target.c[3],
target.c[4], target.c[5], target.c[6], target.c[7]);
target.i[0] = 0xFFFFFFFF;
target.i[1] = 0xFFFFFFFF;
bitfield_write(target.l, src, shift, len);
printf("longwise\n");
printf("0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X\n",
target.c[0], target.c[1], target.c[2], target.c[3],
target.c[4], target.c[5], target.c[6], target.c[7]);
target.i[0] = 0xFFFFFFFF;
target.i[1] = 0xFFFFFFFF;
bitfield_write(target.ll, src, shift, len);
printf("lluwise\n");
printf("0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X\n",
target.c[0], target.c[1], target.c[2], target.c[3],
target.c[4], target.c[5], target.c[6], target.c[7]);
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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists