Attachment 297460 Details for Bug 435456 – Test Program I'm using

Test Program I'm using

bmapspeed.c (text/plain), 10.87 KB, created by Robert Peterson on 2008-03-10 16:46:36 UTC

(hide)

Description:

Filename:

MIME Type:

Creator: Robert Peterson

Created: 2008-03-10 16:46:36 UTC

Size: 10.87 KB

patch

obsolete

>#include <unistd.h>
>#include <stdio.h>
>#include <stdint.h>
>#include <libgen.h>
>#include <sys/types.h>
>#include <sys/stat.h>
>#include <fcntl.h>
>#include <string.h>
>#include <linux/types.h>
>#include <sys/time.h>
>#include <stdlib.h>
>
>#define u8 unsigned char
>#define u32 uint32_t
>
>#define BITBUF_SIZE (50*1024*1024)
>#define GOAL (BITBUF_SIZE / 32)
>#define GFS2_NBBY               4
>#define GFS2_BIT_SIZE           2
>#define GFS2_BIT_MASK           0x00000003
>
>#define BFITNOENT ((uint32_t)~0)
>#define BITS_PER_LONG 64
>
>#define GFS2_BLKST_FREE         0
>#define GFS2_BLKST_USED         1
>#define GFS2_BLKST_UNLINKED     2
>#define GFS2_BLKST_DINODE       3
>
>#define ITER 10
>#define ALIGN(x,a) (((x)+(a)-1)&~((a)-1))
>
>#define TESTS 6
>
>#define BYTENEED0 (0)
>#define BYTENEED1 (1)
>#define BYTESKIP0 (0x55)
>
>#if BITS_PER_LONG == 32
>#define LBITMASK   (0x55555555UL)
>#define LBITSKIP55 (0x55555555UL)
>#define LBITSKIP00 (0x00000000UL)
>#else
>#define LBITMASK   (0x5555555555555555UL)
>#define LBITSKIP55 (0x5555555555555555UL)
>#define LBITSKIP00 (0x0000000000000000UL)
>#endif
>
>struct timeval t1[TESTS], t2[TESTS], timerandfactor;
>unsigned long tdiff[TESTS];
>uint32_t b[TESTS][ITER];
>
>typedef uint32_t (*bitfit_call_t) (const u8 *buffer, unsigned int buflen,
>				   uint32_t goal, u8 old_state);
>
>/* ------------------------------------------------------------------------- */
>/* This is the way gfs2 does it as of 04 March 2008: */
>/* ------------------------------------------------------------------------- */
>static uint32_t gfs2_bitfit(const u8 *buffer, unsigned int buflen,
>			    u32 goal, u8 old_state)
>{
>	const unsigned char *byte;
>	uint32_t blk = goal;
>	unsigned int bit, bitlong;
>	unsigned long *plong, plong55;
>
>	byte = buffer + (goal / GFS2_NBBY);
>	plong = (unsigned long *)(buffer + (goal / GFS2_NBBY));
>	bit = (goal % GFS2_NBBY) * GFS2_BIT_SIZE;
>	bitlong = bit;
>#if BITS_PER_LONG == 32
>	plong55 = 0x55555555;
>#else
>	plong55 = 0x5555555555555555;
>#endif
>	while (byte < buffer + buflen) {
>
>		if (bitlong == 0 && old_state == 0 && *plong == plong55) {
>			plong++;
>			byte += sizeof(unsigned long);
>			blk += sizeof(unsigned long) * GFS2_NBBY;
>			continue;
>		}
>		if (((*byte >> bit) & GFS2_BIT_MASK) == old_state)
>			return blk;
>		bit += GFS2_BIT_SIZE;
>		if (bit >= 8) {
>			bit = 0;
>			byte++;
>		}
>		bitlong += GFS2_BIT_SIZE;
>		if (bitlong >= sizeof(unsigned long) * 8) {
>			bitlong = 0;
>			plong++;
>		}
>
>		blk++;
>	}
>
>	return BFITNOENT;
>}
>
>/* ------------------------------------------------------------------------- */
>/* This is the way gfs2 used to do it before I optimized it on 25 Jan 2008 */
>/* ------------------------------------------------------------------------- */
>static uint32_t gfs2_bitfit2(const u8 *buffer, unsigned int buflen,
>			     u32 goal, u8 old_state)
>{
>	const unsigned char *byte, *end;
>	unsigned char alloc;
>	u32 blk = goal;
>	unsigned int bit;
>
>        byte = buffer + (goal / GFS2_NBBY);
>        bit = (goal % GFS2_NBBY) * GFS2_BIT_SIZE;
>        end = buffer + buflen;
>        alloc = (old_state == GFS2_BLKST_FREE) ? 0x55 : 0;
>
>        while (byte < end) {
>                /* If we're looking for a free block we can eliminate all
>                   bitmap settings with 0x55, which represents four data
>                   blocks in a row.  If we're looking for a data block, we can
>                   eliminate 0x00 which corresponds to four free blocks. */
>                if ((*byte & 0x55) == alloc) {
>			blk += (8 - bit) >> 1;
>			bit = 0;
>			byte++;
>
>			continue;
>		}
>
>		if (((*byte >> bit) & GFS2_BIT_MASK) == old_state)
>			return blk;
>
>		bit += GFS2_BIT_SIZE;
>		if (bit >= 8) {
>			bit = 0;
>			byte++;
>		}
>
>		blk++;
>	}
>
>	return BFITNOENT;
>}
>
>/* ------------------------------------------------------------------------- */
>/* This is experiment 3: */
>/* ------------------------------------------------------------------------- */
>/* Search for "free" blocks */
>static uint32_t gfs2_bitfit3(const u8 *buffer, unsigned int buflen, u32 goal,
>			     u8 old_state)
>{
>	const unsigned char *byte, *start, *end;
>	unsigned int bit, bitlong, startbit;
>	unsigned long *plong;
>
>	start = buffer + (goal / GFS2_NBBY);
>	byte = start;
>        end = buffer + buflen;
>	plong = (unsigned long *)(buffer + (goal / GFS2_NBBY));
>	startbit = bit = (goal % GFS2_NBBY) * GFS2_BIT_SIZE;
>	bitlong = bit;
>	while (byte < end) {
>
>		if (bitlong == 0 && *plong == LBITMASK) {
>			plong++;
>			byte += sizeof(unsigned long);
>			continue;
>		}
>		if (((*byte >> bit) & GFS2_BIT_MASK) == old_state) {
>			return goal +
>				(((byte-start) * GFS2_NBBY) +
>				 (bit / GFS2_BIT_SIZE) -
>				 (startbit / GFS2_BIT_SIZE));
>		}
>		bit += GFS2_BIT_SIZE;
>		if (bit >= 8) {
>			bit = 0;
>			byte++;
>		}
>		bitlong += GFS2_BIT_SIZE;
>		if (bitlong >= sizeof(unsigned long) * 8) {
>			bitlong = 0;
>			plong++;
>		}
>	}
>
>	return BFITNOENT;
>}
>
>/* ------------------------------------------------------------------------- */
>/* This is experiment 4: */
>/* ------------------------------------------------------------------------- */
>/* Search for "free" blocks */
>static uint32_t gfs2_bitfit4(const u8 *buffer, unsigned int buflen,
>			     u32 goal, u8 old_state)
>{
>	const unsigned char *byte, *start, *end;
>	int bit, bitlong, startbit;
>	unsigned long *plong;
>
>	start = buffer + (goal / GFS2_NBBY);
>	byte = start;
>        end = buffer + buflen;
>	plong = (unsigned long *)(buffer + (goal / GFS2_NBBY));
>	startbit = bit = (goal % GFS2_NBBY) * GFS2_BIT_SIZE;
>	bitlong = bit;
>	while (byte < end) {
>
>		if (bitlong == 0 && (*plong == LBITSKIP55)) {
>			plong++;
>			byte += sizeof(unsigned long);
>			continue;
>		}
>		if (bitlong == 0 && ((*plong) & LBITMASK) == LBITSKIP55) {
>			plong++;
>			byte += sizeof(unsigned long);
>			continue;
>		}
>		if (((*byte >> bit) & GFS2_BIT_MASK) == old_state) {
>			return goal +
>				(((byte - start) * GFS2_NBBY) +
>				 ((bit - startbit) / GFS2_BIT_SIZE));
>		}
>		if (bit == (GFS2_NBBY * GFS2_BIT_SIZE) - GFS2_BIT_SIZE) {
>			bit = 0;
>			byte++;
>		} else {
>			bit += GFS2_BIT_SIZE;
>		}
>		bitlong += GFS2_BIT_SIZE;
>		if (bitlong >= sizeof(unsigned long) * GFS2_NBBY *
>		    GFS2_BIT_SIZE) {
>			bitlong = 0;
>			plong++;
>		}
>	}
>
>	return BFITNOENT;
>}
>
>/* ------------------------------------------------------------------------- */
>/* This is algorithm 5: - The is the first one I posted to cluster-devel     */
>/*                        which Steve had suggestions on.                    */
>/* ------------------------------------------------------------------------- */
>static u32 gfs2_bitfit5(const u8 *buffer, unsigned int buflen, u32 goal,
>			u8 old_state)
>{
>	const u8 *byte, *start, *end;
>	int bit, startbit;
>	u32 g1, g2, misaligned;
>	unsigned long *plong;
>	unsigned long lskipval;
>
>	lskipval = (old_state & GFS2_BLKST_USED) ? LBITSKIP00 : LBITSKIP55;
>	g1 = (goal / GFS2_NBBY);
>	start = buffer + g1;
>	byte = start;
>        end = buffer + buflen;
>	g2 = ALIGN(g1, sizeof(unsigned long));
>	plong = (unsigned long *)(buffer + g2);
>	startbit = bit = (goal % GFS2_NBBY) * GFS2_BIT_SIZE;
>	misaligned = g2 - g1;
>	while (byte < end) {
>
>		if (bit == 0 && !misaligned) {
>			if (((*plong) & LBITMASK) == lskipval) {
>				plong++;
>				byte += sizeof(unsigned long);
>				continue;
>			}
>		}
>		if (((*byte >> bit) & GFS2_BIT_MASK) == old_state) {
>			return goal +
>				(((byte - start) * GFS2_NBBY) +
>				 ((bit - startbit) >> 1));
>		}
>		bit += GFS2_BIT_SIZE;
>		if (bit >= GFS2_NBBY * GFS2_BIT_SIZE) {
>			bit = 0;
>			byte++;
>			/* If we were misaligned, adjust the counter */
>			if (misaligned)
>				misaligned--;
>			else { /* If we were aligned, we're not anymore. */
>				misaligned += sizeof(unsigned long) - 1;
>				plong++;
>			}
>		}
>	}
>
>	return BFITNOENT;
>}
>
>/* ------------------------------------------------------------------------- */
>/* This is algorithm 6: - THE FASTEST REVISED */
>/* ------------------------------------------------------------------------- */
>static u32 gfs2_bitfit6(const u8 *buffer, unsigned int buflen, u32 goal,
>		       u8 old_state)
>{
>	const u8 *byte, *start, *end;
>	int bit, startbit;
>	u32 g1, g2, misaligned;
>	unsigned long *plong;
>	unsigned long lskipval;
>
>	lskipval = (old_state & GFS2_BLKST_USED) ? LBITSKIP00 : LBITSKIP55;
>	g1 = (goal / GFS2_NBBY);
>	start = buffer + g1;
>	byte = start;
>        end = buffer + buflen;
>	g2 = ALIGN(g1, sizeof(unsigned long));
>	plong = (unsigned long *)(buffer + g2);
>	startbit = bit = (goal % GFS2_NBBY) * GFS2_BIT_SIZE;
>	misaligned = g2 - g1;
>	if (!misaligned)
>		goto ulong_aligned;
>/* parse the bitmap a byte at a time */
>misaligned:
>	while (byte < end) {
>		if (((*byte >> bit) & GFS2_BIT_MASK) == old_state) {
>			return goal +
>				(((byte - start) * GFS2_NBBY) +
>				 ((bit - startbit) >> 1));
>		}
>		bit += GFS2_BIT_SIZE;
>		if (bit >= GFS2_NBBY * GFS2_BIT_SIZE) {
>			bit = 0;
>			byte++;
>			misaligned--;
>			if (!misaligned) {
>				plong = (unsigned long *)byte;
>				goto ulong_aligned;
>			}
>		}
>	}
>	return BFITNOENT;
>
>/* parse the bitmap a unsigned long at a time */
>ulong_aligned:
>	while ((unsigned char *)plong < end) {
>		if (((*plong) & LBITMASK) == lskipval)
>			plong++;
>		else {
>			byte = (const u8 *)plong;
>			misaligned += sizeof(unsigned long) - 1;
>			goto misaligned;
>		}
>	}
>
>	return BFITNOENT;
>}
>
>/* ------------------------------------------------------------------------- */
>/* timetestfunc - time-test one of the functions */
>/* ------------------------------------------------------------------------- */
>void timetestfunc(bitfit_call_t alg, int testno, unsigned char *buffer)
>{
>	int i;
>
>	gettimeofday(&t1[testno], NULL);
>	for (i = 0; i < ITER; i++) {
>		b[testno][i] = alg(buffer, BITBUF_SIZE, GOAL + i*13,
>				   GFS2_BLKST_FREE);
>		if (b[testno][0] != b[0][i]) {
>			printf("Algorithm %d gave the wrong answer.\n", i);
>			exit(-1);
>		}
>	}
>	gettimeofday(&t2[testno], NULL);
>	tdiff[testno] = (t2[testno].tv_sec - t1[testno].tv_sec) * 1000000;
>	tdiff[testno] += (t2[testno].tv_usec - t1[testno].tv_usec);
>	printf("tdiff[%d] = %7ld  ", testno, tdiff[testno]);
>	printf(" - %f times today's algorithm",
>	       (float)tdiff[0] / (float)tdiff[testno]);
>	printf("\n");
>	fflush(stdout);
>}
>
>/* ------------------------------------------------------------------------- */
>/* main */
>/* ------------------------------------------------------------------------- */
>int main(int argc, char **argv)
>{
>	unsigned char *bitbuffer = NULL;
>	int i, trandfactor;
>	gettimeofday(&timerandfactor, NULL);
>	trandfactor = timerandfactor.tv_usec & 0x7f;
>	if (trandfactor < 8)
>		trandfactor = 101;
>
>	bitbuffer = malloc(BITBUF_SIZE);
>	if (!bitbuffer) {
>		perror("bitbuffer");
>		exit(-1);
>	}
>	memset(bitbuffer, 0x55, BITBUF_SIZE);
>
>	/* Throw in some non-55 noise */
>	printf("trandfactor = %d\n", trandfactor);
>	fflush(stdout);
>	for (i = 1; i < BITBUF_SIZE; i += trandfactor)
>		bitbuffer[i] = 0xff;
>	
>	bitbuffer[BITBUF_SIZE - 100] = 0x00;
>
>	timetestfunc(gfs2_bitfit, 0, bitbuffer);
>	timetestfunc(gfs2_bitfit2, 1, bitbuffer);
>	timetestfunc(gfs2_bitfit3, 2, bitbuffer);
>	timetestfunc(gfs2_bitfit4, 3, bitbuffer);
>	timetestfunc(gfs2_bitfit5, 4, bitbuffer);
>	timetestfunc(gfs2_bitfit6, 5, bitbuffer);
>
>	/* ----------------------------------------------------------------- */
>
>	free(bitbuffer);
>	exit(0);
>}

Actions: View

Attachments on bug 435456: 297261 | 297459 | 297460 | 297533 | 297654 | 297802