From: Alex Pyrgiotis Date: Sun, 10 Mar 2013 11:49:25 +0000 (+0200) Subject: Improve LFSR implementation X-Git-Tag: 0.3~24^2~9 X-Git-Url: https://code.grnet.gr/git/archipelago/commitdiff_plain/b28fa3e7fac89a5db0490e1bd3069ed68a8b27eb Improve LFSR implementation Also, prepare the code for the addition of verification support --- diff --git a/xseg/peers/user/Makefile b/xseg/peers/user/Makefile index b166678..1ccd177 100644 --- a/xseg/peers/user/Makefile +++ b/xseg/peers/user/Makefile @@ -35,7 +35,7 @@ include $(XSEG_HOME)/base.mk PEERS := xseg mt-sosd dummy mt-mapperd pfiled vlmc-xseg st-vlmcd mt-pfiled \ - lfsr bench + bench FILES="Makefile" FILES+=$(shell ls *.h) @@ -72,15 +72,10 @@ xseg: xseg-tool.c $(BASE)/xtypes/xheap.c $(BASE)/xseg/xseg.h mt-sosd: mt-sosd.c peer.c peer.h $(CC) $(CFLAGS) -o $@ $< peer.c $(INC) -L$(LIB) -lxseg -lrados -lpthread \ -lcrypto -DMT - dummy: dummy.c peer.c peer.h $(CC) $(CFLAGS) -o $@ $< peer.c $(INC) -L$(LIB) -lxseg -lpthread -DMT -lfsr: bench-lfsr.c bench-xseg.h peer.h - $(CC) $(CFLAGS) -o $@ $(CPREQS) $(INC) -L$(LIB) -lxseg -lpthread -lm \ - -DSTAND_ALONE - -bench: bench-xseg.c peer.c bench-timer.c bench-lfsr.c bench-utils.c bench-xseg.h peer.h +bench: bench-xseg.c peer.c bench-timer.c bench-lfsr.c bench-utils.c bench-xseg.h peer.h bench-lfsr.h $(CC) $(CFLAGS) -o $@ $(CPREQS) $(INC) -L$(LIB) -lxseg -lpthread -lm monitor: monitor.c peer.c peer.h diff --git a/xseg/peers/user/bench-lfsr.c b/xseg/peers/user/bench-lfsr.c index a7e6637..40ce0fc 100644 --- a/xseg/peers/user/bench-lfsr.c +++ b/xseg/peers/user/bench-lfsr.c @@ -1,89 +1,14 @@ -/* - * Copyright 2012 GRNET S.A. All rights reserved. - * - * Redistribution and use in source and binary forms, with or - * without modification, are permitted provided that the following - * conditions are met: - * -* 1. Redistributions of source code must retain the above -* copyright notice, this list of conditions and the following -* disclaimer. -* 2. Redistributions in binary form must reproduce the above -* copyright notice, this list of conditions and the following -* disclaimer in the documentation and/or other materials -* provided with the distribution. -* -* THIS SOFTWARE IS PROVIDED BY GRNET S.A. ``AS IS'' AND ANY EXPRESS -* OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR -* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL GRNET S.A OR -* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, -* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT -* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF -* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED -* AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT -* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN -* ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE -* POSSIBILITY OF SUCH DAMAGE. -* -* The views and conclusions contained in the software and -* documentation are those of the authors and should not be -* interpreted as representing official policies, either expressed -* or implied, of GRNET S.A. -*/ - #include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include - #include -#ifdef __GNUC__ -#define likely(x) __builtin_expect(!!(x),1) -#define unlikely(x) __builtin_expect(!!(x),0) -#else -#define likely(x) (x) -#define unlikely(x) (x) -#endif - -#define MAX_TAPS 6 - -#ifdef STAND_ALONE -uint64_t global_seed; -#endif +#include /* - * LFSRs are pseudo-random number generators. They are deterministic (meaning - * that the same seed will produce the same number sequence) and extremely - * fast. - * - * You can find more about LFSRs from these links: - * http://en.wikipedia.org/wiki/Linear_feedback_shift_register - * http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf - * http://www.ti.com/lit/an/scta036a/scta036a.pdf - * http://notabs.org/lfsr/lfsr.html - * http://www.electricdruid.net/index.php?page=techniques.practicalLFSRs - * * LFSR taps retrieved from: * http://home1.gte.net/res0658s/electronics/LFSRtaps.html * - * It's common in the bibliography to start the numbering of LFSR bits from 1 - * instead of 0. We will use the same numbering in this code and alter it - * where necessary. - * - * Below is a 64x6 uint8_t array that covers all the appropriate taps for - * maximal length LFSRs, ranging from 3-bits to 64bit. It's memory overhead - * should be relatively small, no more than 384 bytes. + * The memory overhead of the following tap table should be relatively small, + * no more than 400 bytes. */ static uint8_t taps[64][MAX_TAPS] = { @@ -151,153 +76,155 @@ static uint8_t taps[64][MAX_TAPS] = {63, 62}, //Tap position for 63-bit LFSR }; -/* - * There are two kinds of LFSRs, each of which can be implemented with XOR or - * XNOR logic: - * a) Fibonacci LFSRs, that have XOR/XNOR gates serially to produce the input - * bit and - * b) Galois LFSRs, that have XOR/XNOR gates parallely, separated from one - * another and the outputs of which are fed as input bits. Also, the tap bits - * are flipped, depending on the output bit. - * - * A Galois LFSR seems more complicated but is actually the fittest - * implementation for an LFSR on CPU, due to the fact that the input bit can - * be computed on one turn, instead of 2 - 6 that would be needed for a - * Fibonacci LFSR. Another point that must be taken into consideration is - * that an LFSR with XOR gates has the 0 state as illegal, which is something - * we do not want for benchmarks. - * - * That's why we use an Galois-XNOR LFSR. - * - * Below we create what can best be described as an XNOR-mask - */ -static uint64_t lfsr_create_xnormask(uint8_t *taps) -{ - int i; - uint64_t xnormask = 0; +#define __LFSR_NEXT(__lfsr, __v) \ + __v = ((__v >> 1) | __lfsr->cached_bit) ^ \ + (((__v & 1UL) - 1UL) & __lfsr->xormask); - for(i = 0; i < MAX_TAPS && taps[i] != 0; i++) - xnormask |= 1UL << (taps[i] - 1); - - return xnormask; +static inline void __lfsr_next(struct bench_lfsr *lfsr, unsigned int spin) +{ + /* + * This should be O(1) since most compilers will create a jump table for + * this switch. + */ + switch (spin) { + case 16: __LFSR_NEXT(lfsr, lfsr->last_val); + case 15: __LFSR_NEXT(lfsr, lfsr->last_val); + case 14: __LFSR_NEXT(lfsr, lfsr->last_val); + case 13: __LFSR_NEXT(lfsr, lfsr->last_val); + case 12: __LFSR_NEXT(lfsr, lfsr->last_val); + case 11: __LFSR_NEXT(lfsr, lfsr->last_val); + case 10: __LFSR_NEXT(lfsr, lfsr->last_val); + case 9: __LFSR_NEXT(lfsr, lfsr->last_val); + case 8: __LFSR_NEXT(lfsr, lfsr->last_val); + case 7: __LFSR_NEXT(lfsr, lfsr->last_val); + case 6: __LFSR_NEXT(lfsr, lfsr->last_val); + case 5: __LFSR_NEXT(lfsr, lfsr->last_val); + case 4: __LFSR_NEXT(lfsr, lfsr->last_val); + case 3: __LFSR_NEXT(lfsr, lfsr->last_val); + case 2: __LFSR_NEXT(lfsr, lfsr->last_val); + case 1: __LFSR_NEXT(lfsr, lfsr->last_val); + case 0: __LFSR_NEXT(lfsr, lfsr->last_val); + default: break; + } } -/* - * To initialize an LFSR we need the following: - * a) the upper limit of random numbers that we want LFSR to generate (size) - * b) the initial state of LFSR (seed) - * - * NOTE1: If the upper limit is bigger than 63 bits or smaller than 3 bits, we - * cannot create the LFSR. - * NOTE2: If 2^(n+1) < upper_limit <= 2^n , the LFSR that will be created will - * have (n+1) bits. - * NOTE3: If an LFSR has n bits, the seed must not be all ones (= 2^(n+1) - 1) - */ -/* -int lfsr_init(struct lfsr *lfsr, uint64_t size, uint64_t seed) +uint64_t lfsr_next(struct bench_lfsr *lfsr) { - uint8_t i; - - lfsr->limit = size; - - //i has number of bits of size - for (i = 0; size; i++) - size = size >> 1; + int repeat; + unsigned int spin; - if (i < 3 || i > 63) - return -1; + lfsr->num_vals++; - lfsr->length = i; - lfsr->xnormask = lfsr_create_xnormask(taps[i]); + repeat = lfsr->num_vals % lfsr->cycle_length; + if (repeat == 0) + spin = lfsr->spin + 1; + else + spin = lfsr->spin; - if (seed == (1UL << (i + 1)) - 1) - return -1; + do { + __lfsr_next(lfsr, spin); + } while (lfsr->last_val > lfsr->max_val); - lfsr->state = seed; - return 0; + return lfsr->last_val; } -*/ -int lfsr_init(struct lfsr *lfsr, uint64_t size, uint64_t seed) -{ - uint8_t i; - lfsr->limit = size; +static uint64_t lfsr_create_xormask(uint8_t *taps) +{ + int i; + uint64_t xormask = 0; - //`i` has required number of bits for LFSR - for (i = 3; size >= (1UL << i); i++) {} + for(i = 0; i < MAX_TAPS && taps[i] != 0; i++) + xormask |= 1UL << (taps[i] - 1); - //Will not create LFSR longer than 63 bits - if (i > 63) - return -1; + return xormask; +} - //The all ones state is illegal. Due to the fact that our seed is - //nanoseconds taken from clock_gettime, we are sure that the 31st bit will - //always be 0. The following codes has that in mind and creates a seed - //that has at least one 0. - //FIXME: The above wrong, we cannot assume seed is taken from timer. - if (seed == UINT64_MAX) { - if (i < 32) - lfsr->state = global_seed >> (31 - i); - else - lfsr->state = global_seed << (i - 31); - } else { - lfsr->state = seed; - } +static uint8_t *find_lfsr(uint64_t size) +{ + int i; - lfsr->cached_bit = 1UL << (i-1); - lfsr->length = i; - lfsr->xnormask = lfsr_create_xnormask(taps[i]); + for (i = 3; i < 64; i++) + if ((1UL << i) > size) /* TODO: Explain why. */ + return taps[i]; - return 0; + return NULL; } -#ifdef STAND_ALONE /* - * Sanity-check every LFSR for mistakes. + * It is well-known that all maximal n-bit LFSRs will start repeating + * themselves after their 2^n iteration. The introduction of spins however, is + * possible to create a repetition of a sub-sequence before we hit that mark. + * This happens if: + * + * [1]: ((2^n - 1) * i) % (spin + 1) == 0, + * where "n" is LFSR's bits and "i" any number within the range [1,spin] + * + * It is important to know beforehand if a spin can cause a repetition of a + * sub-sequence (cycle) and its length. However, calculating (2^n - 1) * i may + * produce a buffer overflow for "n" close to 64, so we expand the above to: + * + * [2]: (2^n - 1) -> (x * (spin + 1) + y), where x >= 0 and 0 <= y <= spin + * + * Thus, [1] is equivalent to (y * i) % (spin + 1) == 0; + * Also, the cycle's length will be (x * i) + (y * i) / (spin + 1) */ -static int lfsr_check() +int prepare_spin(struct bench_lfsr *lfsr, unsigned int spin) { - struct lfsr lfsr; - uint8_t length, i; - uint64_t period; - uint64_t upper_limit; + uint64_t max = (lfsr->cached_bit << 1) - 1; + uint64_t x, y; + int i; - //Create all LFSRs with maximum limit - for (length = 3; length < 64; length++) { - if (lfsr_init(&lfsr, pow(2, length) - 1, 1)) - return -1; - // printf("XNOR-mask: %lu, state: %lu, limit: %lu\n", - // lfsr.xnormask, lfsr.state, lfsr.limit); - period = 1; //Already initialized at 1 - upper_limit = pow(2, length); + if (spin > 15) + return 1; - while(likely(period++ < upper_limit)) - lfsr_next(&lfsr); + x = max / (spin + 1); + y = max % (spin + 1); + lfsr->cycle_length = max; /* This is the expected cycle */ + lfsr->spin = spin; - if (lfsr.state == 1) { - printf("%u-bit LFSR is correct\n", length); - } - else { - printf("%u-bit LFSR did not iterate successfully\n", length); - printf("Current tap positions: "); - for (i = 0; i < MAX_TAPS && taps[length][i] != 0; i++) - printf("%u ", taps[length][i]); - printf("\n"); - return -1; + for (i = 1; i <= spin; i++) { + if ((y * i) % (spin + 1) == 0) { + lfsr->cycle_length = (x * i) + (y * i) / (spin + 1); + break; } - // return 0; } return 0; } -int main() +int lfsr_reset(struct bench_lfsr *lfsr, unsigned long seed) { - int r; + uint64_t bitmask = (lfsr->cached_bit << 1) - 1; - r = lfsr_check(); + lfsr->num_vals = 0; + lfsr->last_val = seed & bitmask; - return r; + /* All-ones state is illegal for XNOR LFSRs */ + if (lfsr->last_val == bitmask) + return 1; + + return 0; +} + +int lfsr_init(struct bench_lfsr *lfsr, uint64_t nums, unsigned long seed, + unsigned int spin) +{ + uint8_t *lfsr_taps; + + lfsr_taps = find_lfsr(nums); + if (!lfsr_taps) + return 1; + + lfsr->max_val = nums - 1; + lfsr->xormask = lfsr_create_xormask(lfsr_taps); + lfsr->cached_bit = 1UL << (lfsr_taps[0] - 1); + + if (prepare_spin(lfsr, spin)) + return 1; + + if (lfsr_reset(lfsr, seed)) + return 1; + + return 0; } -#endif diff --git a/xseg/peers/user/bench-lfsr.h b/xseg/peers/user/bench-lfsr.h new file mode 100644 index 0000000..75f6089 --- /dev/null +++ b/xseg/peers/user/bench-lfsr.h @@ -0,0 +1,27 @@ +#ifndef FIO_LFSR_H +#define FIO_LFSR_H +#include + +#define MAX_TAPS 6 + +struct lfsr_taps { + unsigned int length; + unsigned int taps[MAX_TAPS]; +}; + + +struct bench_lfsr { + uint64_t xormask; + uint64_t last_val; + uint64_t cached_bit; + uint64_t max_val; + uint64_t num_vals; + uint64_t cycle_length; + unsigned int spin; +}; + +uint64_t lfsr_next(struct bench_lfsr *lfsr); +int lfsr_init(struct bench_lfsr *lfsr, uint64_t size, + unsigned long seed, unsigned int spin); +int lfsr_reset(struct bench_lfsr *lfsr, unsigned long seed); +#endif diff --git a/xseg/peers/user/bench-utils.c b/xseg/peers/user/bench-utils.c index c8e8464..06b3471 100644 --- a/xseg/peers/user/bench-utils.c +++ b/xseg/peers/user/bench-utils.c @@ -93,35 +93,44 @@ static double timespec2double(struct timespec num) int read_insanity(char *insanity) { - if (strcmp(insanity, "sane") == 0) + if (strncmp(insanity, "sane", MAX_ARG_LEN + 1) == 0) return TM_SANE; - if (strcmp(insanity, "eccentric") == 0) + if (strncmp(insanity, "eccentric", MAX_ARG_LEN + 1) == 0) return TM_ECCENTRIC; - if (strcmp(insanity, "manic") == 0) + if (strncmp(insanity, "manic", MAX_ARG_LEN + 1) == 0) return TM_MANIC; - if (strcmp(insanity, "paranoid") == 0) + if (strncmp(insanity, "paranoid", MAX_ARG_LEN + 1) == 0) return TM_PARANOID; return -1; } int read_op(char *op) { - if (strcmp(op, "read") == 0) + if (strncmp(op, "read", MAX_ARG_LEN + 1) == 0) return X_READ; - if (strcmp(op, "write") == 0) + if (strncmp(op, "write", MAX_ARG_LEN + 1) == 0) return X_WRITE; - if (strcmp(op, "info") == 0) + if (strncmp(op, "info", MAX_ARG_LEN + 1) == 0) return X_INFO; - if (strcmp(op, "delete") == 0) + if (strncmp(op, "delete", MAX_ARG_LEN + 1) == 0) return X_DELETE; return -1; } +int read_verify(char *verify) +{ + if (strncmp(verify, "no", MAX_ARG_LEN + 1) == 0) + return VERIFY_NO; + if (strncmp(verify, "meta", MAX_ARG_LEN + 1) == 0) + return VERIFY_META; + return -1; +} + int read_pattern(char *pattern) { - if (strcmp(pattern, "seq") == 0) + if (strncmp(pattern, "seq", MAX_ARG_LEN + 1) == 0) return IO_SEQ; - if (strcmp(pattern, "rand") == 0) + if (strncmp(pattern, "rand", MAX_ARG_LEN + 1) == 0) return IO_RAND; return -1; } @@ -191,6 +200,17 @@ void print_res(struct bench *prefs, struct timer *tm, char *type) //TODO: Add std } +//FIXME: this looks like a hack, handle it more elegantly +void create_id(unsigned long seed) +{ + if (seed > pow(10, 9)) + XSEGLOG2(&lc, W, "Seed larger than 10^9, only its first 9 digits will " + "be used\n"); + + //nanoseconds can't be more than 9 digits + snprintf(global_id, IDLEN, "bench-%09lu", seed); +} + void create_target(struct bench *prefs, struct xseg_request *req, uint64_t new) { @@ -228,18 +248,3 @@ uint64_t determine_next(struct bench *prefs) } } -//FIXME: this looks like a hack, handle it more elegantly -void create_id(unsigned long seed) -{ - struct timespec timer_seed; - - if (seed != -1) { - global_seed = seed; - } else { - clock_gettime(CLOCK_MONOTONIC_RAW, &timer_seed); - global_seed = timer_seed.tv_nsec; - } - //nanoseconds can't be more than 9 digits - snprintf(global_id, IDLEN, "bench-%09lu", global_seed); - XSEGLOG2(&lc, I, "Global ID is %s\n", global_id); -} diff --git a/xseg/peers/user/bench-xseg.c b/xseg/peers/user/bench-xseg.c index 920c3e2..4ecfe01 100644 --- a/xseg/peers/user/bench-xseg.c +++ b/xseg/peers/user/bench-xseg.c @@ -45,13 +45,13 @@ #include #include #include +#include #include char global_id[IDLEN]; -uint64_t global_seed; /* - * This function checks two things: + * This macro checks two things: * a) If in-flight requests are less than given iodepth * b) If we have submitted all of the requests */ @@ -72,7 +72,7 @@ void custom_peer_usage() " -tp | None | Target port\n" " --iodepth | 1 | Number of in-flight I/O requests\n" " --verify | no | Verify written requests [no|meta|hash]\n" - " --seed | None | Inititalize LFSR and target names\n" + " --seed | None | Initialize LFSR and target names\n" " --insanity| sane | Adjust insanity level of benchmark:\n" " | | [sane|eccentric|manic|paranoid]\n" "\n"); @@ -88,11 +88,14 @@ int custom_peer_init(struct peerd *peer, int argc, char *argv[]) char op[MAX_ARG_LEN + 1]; char pattern[MAX_ARG_LEN + 1]; char insanity[MAX_ARG_LEN + 1]; + char verify[MAX_ARG_LEN + 1]; struct xseg *xseg = peer->xseg; unsigned int xseg_page_size = 1 << xseg->config.page_shift; long iodepth = -1; long dst_port = -1; unsigned long seed = -1; + struct timespec timer_seed; + int set_by_hand = 0; int r; op[0] = 0; @@ -102,6 +105,7 @@ int custom_peer_init(struct peerd *peer, int argc, char *argv[]) block_size[0] = 0; object_size[0] = 0; insanity[0] = 0; + verify[0] = 0; #ifdef MT for (i = 0; i < nr_threads; i++) { @@ -132,6 +136,7 @@ int custom_peer_init(struct peerd *peer, int argc, char *argv[]) READ_ARG_ULONG("-tp", dst_port); READ_ARG_ULONG("--seed", seed); READ_ARG_STRING("--insanity", insanity, MAX_ARG_LEN); + READ_ARG_STRING("--verify", verify, MAX_ARG_LEN); END_READ_ARGS(); /*****************************\ @@ -139,7 +144,7 @@ int custom_peer_init(struct peerd *peer, int argc, char *argv[]) \*****************************/ //We support 4 xseg operations: X_READ, X_WRITE, X_DELETE, X_INFO - //The I/O pattern of thesee operations can be either synchronous (sync) or + //The I/O pattern of these operations can be either sequential (seq) or //random (rand) if (!op[0]) { XSEGLOG2(&lc, E, "xseg operation needs to be supplied\n"); @@ -163,7 +168,16 @@ int custom_peer_init(struct peerd *peer, int argc, char *argv[]) } prefs->flags |= (uint8_t)r; - //Defailt iodepth value is 1 + if (!verify[0]) + strcpy(verify, "no"); + r = read_verify(verify); + if (r < 0) { + XSEGLOG2(&lc, E, "Invalid syntax: --verify %s\n", verify); + goto arg_fail; + } + + + //Default iodepth value is 1 if (iodepth < 0) prefs->iodepth = 1; else @@ -305,22 +319,33 @@ int custom_peer_init(struct peerd *peer, int argc, char *argv[]) prefs->peer = peer; - //The following function initializes the global_id, global_seed extern - //variables. +reseed: + //We proceed to initialise the global_id, and seed variables. + if (seed == -1) { + clock_gettime(CLOCK_MONOTONIC_RAW, &timer_seed); + seed = timer_seed.tv_nsec; + } else { + set_by_hand = 1; + } create_id(seed); - if ((prefs->flags & (1 <lfsr = malloc(sizeof(struct lfsr)); + if ((prefs->flags & (1 << PATTERN_FLAG)) == IO_RAND) { + prefs->lfsr = malloc(sizeof(struct bench_lfsr)); if (!prefs->lfsr) { perror("malloc"); goto lfsr_fail; } - //FIXME: handle better the seed passing than just giving UINT64_MAX - if (lfsr_init(prefs->lfsr, prefs->max_requests, seed)) { + + r = lfsr_init(prefs->lfsr, prefs->max_requests, seed, seed & 0xF); + if (r && set_by_hand) { XSEGLOG2(&lc, E, "LFSR could not be initialized\n"); goto lfsr_fail; + } else if (r) { + seed = -1; + goto reseed; } } + XSEGLOG2(&lc, I, "Global ID is %s\n", global_id); peer->peerd_loop = custom_peerd_loop; peer->priv = (void *) prefs; @@ -355,7 +380,7 @@ static int send_request(struct peerd *peer, struct bench *prefs) //srcport and dstport must already be provided by the user. //returns struct xseg_request with basic initializations - //XSEGLOG2(&lc, D, "Get new request\n"); + XSEGLOG2(&lc, D, "Get new request\n"); timer_start(prefs, prefs->get_tm); req = xseg_get_request(xseg, srcport, dstport, X_ALLOC); if (!req) { @@ -365,7 +390,7 @@ static int send_request(struct peerd *peer, struct bench *prefs) timer_stop(prefs, prefs->get_tm, NULL); //Allocate enough space for the data and the target's name - //XSEGLOG2(&lc, D, "Prepare new request\n"); + XSEGLOG2(&lc, D, "Prepare new request\n"); r = xseg_prep_request(xseg, req, TARGETLEN, size); if (r < 0) { XSEGLOG2(&lc, W, "Cannot prepare request! (%lu, %llu)\n", @@ -376,7 +401,7 @@ static int send_request(struct peerd *peer, struct bench *prefs) //Determine what the next target/chunk will be, based on I/O pattern new = determine_next(prefs); XSEGLOG2(&lc, I, "Our new request is %lu\n", new); - //Create a target of this format: "bench-" + //Create a target of this format: "bench--" create_target(prefs, req, new); if (prefs->op == X_WRITE || prefs->op == X_READ) { @@ -392,7 +417,7 @@ static int send_request(struct peerd *peer, struct bench *prefs) req->op = prefs->op; //Measure this? - //XSEGLOG2(&lc, D, "Allocate peer request\n"); + XSEGLOG2(&lc, D, "Allocate peer request\n"); pr = alloc_peer_req(peer); if (!pr) { XSEGLOG2(&lc, W, "Cannot allocate peer request (%ld remaining)\n", @@ -426,7 +451,7 @@ static int send_request(struct peerd *peer, struct bench *prefs) memcpy(pr->priv, &prefs->rec_tm->start_time, sizeof(struct timespec)); //Submit the request from the source port to the target port - //XSEGLOG2(&lc, D, "Submit request %lu\n", new); + XSEGLOG2(&lc, D, "Submit request %lu\n", new); timer_start(prefs, prefs->sub_tm); p = xseg_submit(xseg, req, srcport, X_ALLOC); if (p == NoPort) { diff --git a/xseg/peers/user/bench-xseg.h b/xseg/peers/user/bench-xseg.h index 907dbc9..ddfefd7 100644 --- a/xseg/peers/user/bench-xseg.h +++ b/xseg/peers/user/bench-xseg.h @@ -32,6 +32,8 @@ * or implied, of GRNET S.A. */ +#include + #define MAX_ARG_LEN 10 #define TM_SANE 0 @@ -48,14 +50,22 @@ #define IO_RAND 1 << PATTERN_FLAG /* - * FIXME: The following are variables and definitions used to name objects and - * seed the lfsr. They can be handled more elegantly (e.g. be a member of a - * struct.) + * Verify mode occupies second flag bit. + * If 1, it uses metadata for verification, if 0, it's off. + */ +#define VERIFY_FLAG 1 +#define VERIFY_NO 0 << VERIFY_FLAG +#define VERIFY_META 1 << VERIFY_FLAG + +/* + * The benchark ID (IDLEN) is global for the test, calculated once and is a + * string of the following form: {"bench-" + 9-digit number + "\0"}. + * The target string (TARGETLEN) is per object, concatenated with the string + * above and is of the following form: {"-" +16-digit number + "\0"}. */ #define IDLEN 16 #define TARGETLEN (IDLEN + 17) extern char global_id[IDLEN]; -extern uint64_t global_seed; struct bench { uint64_t to; //Total number of objects (not for read/write) @@ -70,7 +80,7 @@ struct bench { uint32_t op; //xseg operation uint8_t flags; struct peerd *peer; - struct lfsr *lfsr; + struct bench_lfsr *lfsr; struct timer *total_tm; //Total time for benchmark struct timer *get_tm; //Time for xseg_get_request struct timer *sub_tm; //Time for xseg_submit_request @@ -112,13 +122,14 @@ struct tm_result { unsigned int ns; }; -/* FILLME +/* FILLME */ struct signature { - //target's name - //οffset + char obj_name[TARGETLEN]; + uint64_t offset; + uint64_t size; + //hash of data (heavy) }; -*/ int custom_peerd_loop(void *arg); @@ -131,6 +142,7 @@ uint64_t str2num(char *str); int read_op(char *op); int read_pattern(char *pattern); int read_insanity(char *insanity); +int read_verify(char *insanity); void print_res(struct bench *prefs, struct timer *tm, char *type); void print_stats(struct bench *prefs); void create_target(struct bench *prefs, struct xseg_request *req, @@ -138,36 +150,5 @@ void create_target(struct bench *prefs, struct xseg_request *req, void create_chunk(struct bench *prefs, struct xseg_request *req, uint64_t new); uint64_t determine_next(struct bench *prefs); -void create_id(); - -/**************\ - * LFSR stuff * -\**************/ - -struct lfsr { - uint64_t state; - uint64_t xnormask; - uint64_t cached_bit; //It's faster if it's on the same cacheline - uint64_t limit; - uint8_t length; -}; - -int lfsr_init(struct lfsr *lfsr, uint64_t size, uint64_t seed); - -/* - * This loop generates each time a new pseudo-random number. However, if it's - * bigger than what we want, we discard it and generate the next one. - */ -static inline uint64_t lfsr_next(struct lfsr *lfsr) -{ - do { - lfsr->state = ((lfsr->state >> 1) | lfsr->cached_bit) ^ - (((lfsr->state & 1UL) - 1UL) & lfsr->xnormask); - //lfsr->state = (lfsr->state >> 1) ^ (-(lfsr->state & 1UL) & lfsr->xnormask); - //printf("State: %lu\n", lfsr->state); - } while (lfsr->state >= lfsr->limit); - //} while (lfsr->state > lfsr->limit); - //printf("------------\n"); - return lfsr->state; -} +void create_id(unsigned long seed);