plugins/sparse-random/sparse-random.c

   1 /* nbdkit
   2  * Copyright Red Hat
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are
   6  * met:
   7  *
   8  * * Redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer.
  10  *
  11  * * Redistributions in binary form must reproduce the above copyright
  12  * notice, this list of conditions and the following disclaimer in the
  13  * documentation and/or other materials provided with the distribution.
  14  *
  15  * * Neither the name of Red Hat nor the names of its contributors may be
  16  * used to endorse or promote products derived from this software without
  17  * specific prior written permission.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY RED HAT AND CONTRIBUTORS ''AS IS'' AND
  20  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
  21  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
  22  * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL RED HAT OR
  23  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  24  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  25  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  26  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  27  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  28  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  29  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30  * SUCH DAMAGE.
  31  */
  32
  33 #include <config.h>
  34
  35 #include <stdio.h>
  36 #include <stdlib.h>
  37 #include <stdint.h>
  38 #include <inttypes.h>
  39 #include <string.h>
  40 #include <errno.h>
  41 #include <time.h>
  42
  43 #define NBDKIT_API_VERSION 2
  44 #include <nbdkit-plugin.h>
  45
  46 #include "bitmap.h"
  47 #include "cleanup.h"
  48 #include "isaligned.h"
  49 #include "iszero.h"
  50 #include "minmax.h"
  51 #include "random.h"
  52
  53 static int64_t size = 0;        /* Size of the disk in bytes. */
  54 static uint32_t seed;           /* Random seed. */
  55 static double percent = 10;     /* Percentage of data. */
  56 static uint64_t runlength =     /* Expected average run length of data (bytes)*/
  57   UINT64_C (16*1024*1024);
  58 static int random_content;      /* false: Repeat same byte  true: Random bytes*/
  59
  60 /* We need to store 1 bit per block.  Using a 4K block size means we
  61  * need 32M to map each 1T of virtual disk.
  62  */
  63 #define BLOCKSIZE 4096
  64
  65 static struct bitmap bm;        /* Bitmap of data blocks. */
  66
  67 static void
  68 sparse_random_load (void)
  69 {
  70   /* Set the seed to a random-ish value.  This is not meant to be
  71    * cryptographically useful.  It can be overridden using the seed
  72    * parameter.
  73    */
  74   seed = time (NULL);
  75
  76   bitmap_init (&bm, BLOCKSIZE, 1 /* bits per block */);
  77 }
  78
  79 static void
  80 sparse_random_unload (void)
  81 {
  82   bitmap_free (&bm);
  83 }
  84
  85 static int
  86 sparse_random_config (const char *key, const char *value)
  87 {
  88   int64_t r;
  89
  90   if (strcmp (key, "seed") == 0) {
  91     if (nbdkit_parse_uint32_t ("seed", value, &seed) == -1)
  92       return -1;
  93   }
  94   else if (strcmp (key, "size") == 0) {
  95     r = nbdkit_parse_size (value);
  96     if (r == -1)
  97       return -1;
  98     size = r;
  99   }
 100   else if (strcmp (key, "percent") == 0) {
 101     if (sscanf (value, "%lf", &percent) != 1 ||
 102         percent < 0 || percent > 100) {
 103       nbdkit_error ("cannot parse percent parameter: %s", value);
 104       return -1;
 105     }
 106   }
 107   else if (strcmp (key, "runlength") == 0) {
 108     if (nbdkit_parse_uint64_t ("runlength", value, &runlength) == -1)
 109       return -1;
 110     if (runlength <= 0) {
 111       nbdkit_error ("runlength parameter must be > 0");
 112       return -1;
 113     }
 114   }
 115   else if (strcmp (key, "random-content") == 0) {
 116     random_content = nbdkit_parse_bool (value);
 117     if (random_content == -1)
 118       return -1;
 119   }
 120   else {
 121     nbdkit_error ("unknown parameter '%s'", key);
 122     return -1;
 123   }
 124
 125   return 0;
 126 }
 127
 128 #define sparse_random_config_help \
 129   "size=<SIZE>  (required) Size of the backing disk\n" \
 130   "seed=<SEED>             Random number generator seed\n" \
 131   "percent=<PERCENT>       Percentage of data\n" \
 132   "runlength=<BYTES>       Expected average run length of data\n" \
 133   "random-content=true     Fully random content in each block"
 134
 135 /* Create the random bitmap of data and holes.
 136  *
 137  * We could independently set each block to a random value, but the
 138  * result wouldn't look much like a virtual machine disk image.
 139  * Instead we use a strategy which tries to produce runs of data
 140  * blocks and hole blocks.  We iterate over the blocks keeping track
 141  * of a current state which is either DATA or HOLE.
 142  *
 143  * When in state DATA, we will flip to state HOLE after each block
 144  * with probability Pᴰᴴ.
 145  *
 146  * When in state HOLE, we will flip to state DATA after each block
 147  * with probability Pᴴᴰ.
 148  *
 149  * This will produce runs like this:
 150  * ◻◻◻◻◻◻◼◼◼◼◻◻◻◻◻◻◻◻◼◼◼◼◼◼◻◻◻◻◻◻◻◻◻◼◼◼◻◻◻◻◻◻◻◻◻◻◻◼◼◼◼◻◻◻◻◻◻◻◻
 151  * ◼ data block   ◻ hole block
 152  *
 153  * By choosing the probabilities Pᴰᴴ and Pᴴᴰ carefully we can target
 154  * both the desired percentage of data, and the average run length of
 155  * data blocks, as follows:
 156  *
 157  * % data = Pᴴᴰ / (Pᴴᴰ + Pᴰᴴ)
 158  * average run length = 1 / Pᴰᴴ
 159  *
 160  * For example, to achieve the defaults (percent = 10%, runlength =
 161  * 16M = 4096 blocks), we would use:
 162  *
 163  * Pᴰᴴ = 1 / runlength
 164  *     = 1 / 4096
 165  *     = 0.000244141
 166  *
 167  * Pᴴᴰ = percent * Pᴰᴴ / (1 - percent)
 168  *     = 0.10 * (1/4096) / (1 - 0.10)
 169  *     = 0.000027127
 170  */
 171 static int
 172 sparse_random_get_ready (void)
 173 {
 174   double P_dh, P_hd, P;
 175   uint64_t i;
 176   int state = 0 /* 0 = HOLE, 1 = DATA */;
 177   struct random_state rs;
 178   uint64_t nr_data_blocks = 0;
 179   uint64_t nr_data_runs = 0;
 180   uint64_t data_run_length = 0;
 181   uint64_t avg_data_run_length = 0;
 182
 183   if (bitmap_resize (&bm, size) == -1)
 184     return -1;
 185
 186   /* A few special cases first. */
 187   if (percent == 0)
 188     return 0;
 189   if (percent == 100) {
 190     bitmap_for (&bm, i) {
 191       bitmap_set_blk (&bm, i, 1);
 192     }
 193     return 0;
 194   }
 195
 196   /* Otherwise calculate the probability parameters as above. */
 197   P_dh = 1. / ((double) runlength / BLOCKSIZE);
 198   P_hd = (percent / 100.) * P_dh / (1. - (percent / 100.));
 199
 200   nbdkit_debug ("percent requested = %g%%, "
 201                 "expected average run length = %" PRIu64,
 202                 percent, runlength);
 203   nbdkit_debug ("Pᴰᴴ = %g, Pᴴᴰ = %g", P_dh, P_hd);
 204
 205   xsrandom (seed, &rs);
 206
 207   bitmap_for (&bm, i) {
 208     if (state) bitmap_set_blk (&bm, i, state);
 209
 210     /* The probability of exiting this state.  If we're in data
 211      * (state != 0) then it's Pᴰᴴ (data->hole), otherwise it's Pᴴᴰ
 212      * (hole->data).
 213      */
 214     P = state ? P_dh : P_hd;
 215     if (xrandom (&rs) <= P * (double) UINT64_MAX)
 216       state ^= 1;
 217   }
 218
 219   /* This code is simply for calculating how well we did compared to
 220    * the target.
 221    */
 222   bitmap_for (&bm, i) {
 223     state = bitmap_get_blk (&bm, i, 0);
 224     if (state == 1) {
 225       nr_data_blocks++;
 226       if (i == 0 || bitmap_get_blk (&bm, i-1, 0) == 0) {
 227         /* Start of new data run. */
 228         avg_data_run_length += data_run_length;
 229         nr_data_runs++;
 230         data_run_length = 1;
 231       }
 232       else
 233         data_run_length++;
 234     }
 235   }
 236   avg_data_run_length += data_run_length;
 237   if (nr_data_runs > 0)
 238     avg_data_run_length /= nr_data_runs;
 239   else
 240     avg_data_run_length = 0;
 241   nbdkit_debug ("percent actual = %g%%, "
 242                 "average run length = %" PRIu64,
 243                 100. * BLOCKSIZE * nr_data_blocks / size,
 244                 avg_data_run_length * BLOCKSIZE);
 245
 246   return 0;
 247 }
 248
 249 #define THREAD_MODEL NBDKIT_THREAD_MODEL_PARALLEL
 250
 251 /* Create the per-connection handle. */
 252 static void *
 253 sparse_random_open (int readonly)
 254 {
 255   return NBDKIT_HANDLE_NOT_NEEDED;
 256 }
 257
 258 /* Get the disk size. */
 259 static int64_t
 260 sparse_random_get_size (void *handle)
 261 {
 262   return size;
 263 }
 264
 265 /* Serves the same data over multiple connections. */
 266 static int
 267 sparse_random_can_multi_conn (void *handle)
 268 {
 269   return 1;
 270 }
 271
 272 /* Cache. */
 273 static int
 274 sparse_random_can_cache (void *handle)
 275 {
 276   /* Everything is already in memory, returning this without
 277    * implementing .cache lets nbdkit do the correct no-op.
 278    */
 279   return NBDKIT_CACHE_NATIVE;
 280 }
 281
 282 static void
 283 read_block (uint64_t blknum, uint64_t offset, void *buf)
 284 {
 285   unsigned char *b = buf;
 286   uint64_t s;
 287   uint32_t i;
 288   struct random_state state;
 289
 290   if (bitmap_get_blk (&bm, blknum, 0) == 0) /* hole */
 291     memset (buf, 0, BLOCKSIZE);
 292   else if (!random_content) {   /* data when random-content=false */
 293     xsrandom (seed + offset, &state);
 294     s = xrandom (&state);
 295     s &= 255;
 296     if (s == 0) s = 1;
 297     memset (buf, (int)s, BLOCKSIZE);
 298   }
 299   else {                        /* data when random-content=true */
 300     /* This produces repeatable data for the same offset.  Note it
 301      * works because we are called on whole blocks only.
 302      */
 303     xsrandom (seed + offset, &state);
 304     for (i = 0; i < BLOCKSIZE; ++i) {
 305       s = xrandom (&state);
 306       s &= 255;
 307       b[i] = s;
 308     }
 309   }
 310 }
 311
 312 /* Read data. */
 313 static int
 314 sparse_random_pread (void *handle, void *buf, uint32_t count, uint64_t offset,
 315                      uint32_t flags)
 316 {
 317   CLEANUP_FREE uint8_t *block = NULL;
 318   uint64_t blknum, blkoffs;
 319
 320   if (!IS_ALIGNED (count | offset, BLOCKSIZE)) {
 321     block = malloc (BLOCKSIZE);
 322     if (block == NULL) {
 323       nbdkit_error ("malloc: %m");
 324       return -1;
 325     }
 326   }
 327
 328   blknum = offset / BLOCKSIZE;  /* block number */
 329   blkoffs = offset % BLOCKSIZE; /* offset within the block */
 330
 331   /* Unaligned head */
 332   if (blkoffs) {
 333     uint64_t n = MIN (BLOCKSIZE - blkoffs, count);
 334
 335     read_block (blknum, offset, block);
 336     memcpy (buf, &block[blkoffs], n);
 337
 338     buf += n;
 339     count -= n;
 340     offset += n;
 341     blknum++;
 342   }
 343
 344   /* Aligned body */
 345   while (count >= BLOCKSIZE) {
 346     read_block (blknum, offset, buf);
 347
 348     buf += BLOCKSIZE;
 349     count -= BLOCKSIZE;
 350     offset += BLOCKSIZE;
 351     blknum++;
 352   }
 353
 354   /* Unaligned tail */
 355   if (count) {
 356     read_block (blknum, offset, block);
 357     memcpy (buf, block, count);
 358   }
 359
 360   return 0;
 361 }
 362
 363 /* Write data.
 364  *
 365  * This actually checks that what you're writing exactly matches
 366  * what is expected.
 367  */
 368 static int
 369 sparse_random_pwrite (void *handle, const void *buf,
 370                       uint32_t count, uint64_t offset,
 371                       uint32_t flags)
 372 {
 373   CLEANUP_FREE uint8_t *block;
 374   uint64_t blknum, blkoffs;
 375
 376   block = malloc (BLOCKSIZE);
 377   if (block == NULL) {
 378     nbdkit_error ("malloc: %m");
 379     return -1;
 380   }
 381
 382   blknum = offset / BLOCKSIZE;  /* block number */
 383   blkoffs = offset % BLOCKSIZE; /* offset within the block */
 384
 385   /* Unaligned head */
 386   if (blkoffs) {
 387     uint64_t n = MIN (BLOCKSIZE - blkoffs, count);
 388
 389     read_block (blknum, offset, block);
 390     if (memcmp (buf, &block[blkoffs], n) != 0) {
 391     unexpected_data:
 392       errno = EIO;
 393       nbdkit_error ("data written does not match expected");
 394       return -1;
 395     }
 396
 397     buf += n;
 398     count -= n;
 399     offset += n;
 400     blknum++;
 401   }
 402
 403   /* Aligned body */
 404   while (count >= BLOCKSIZE) {
 405     /* As an optimization, skip calling read_block if we know this is
 406      * a hole.  Call is_zero instead which should be faster.
 407      */
 408     if (bitmap_get_blk (&bm, blknum, 0) == 0) {
 409       if (! is_zero (buf, BLOCKSIZE))
 410         goto unexpected_data;
 411     }
 412     else {
 413       read_block (blknum, offset, block);
 414       if (memcmp (buf, block, BLOCKSIZE) != 0)
 415         goto unexpected_data;
 416     }
 417
 418     buf += BLOCKSIZE;
 419     count -= BLOCKSIZE;
 420     offset += BLOCKSIZE;
 421     blknum++;
 422   }
 423
 424   /* Unaligned tail */
 425   if (count) {
 426     read_block (blknum, offset, block);
 427     if (memcmp (buf, block, count) != 0)
 428       goto unexpected_data;
 429   }
 430
 431   return 0;
 432 }
 433
 434 /* Flush.
 435  *
 436  * This is required in order to support the nbdcopy --flush option,
 437  * but it's a no-op since this plugin does not store data.
 438  */
 439 static int
 440 sparse_random_flush (void *handle, uint32_t flags)
 441 {
 442   return 0;
 443 }
 444
 445 /* Trim and zero.
 446  *
 447  * These only let you "write" to holes.
 448  */
 449 static int
 450 sparse_random_trim_zero (void *handle, uint32_t count, uint64_t offset,
 451                          uint32_t flags)
 452 {
 453   uint64_t blknum, blkoffs;
 454
 455   blknum = offset / BLOCKSIZE;  /* block number */
 456   blkoffs = offset % BLOCKSIZE; /* offset within the block */
 457
 458   /* Unaligned head */
 459   if (blkoffs) {
 460     uint64_t n = MIN (BLOCKSIZE - blkoffs, count);
 461
 462     if (bitmap_get_blk (&bm, blknum, 0) != 0) {
 463     unexpected_trim:
 464       errno = EIO;
 465       nbdkit_error ("trying to trim or zero non-hole in disk");
 466       return -1;
 467     }
 468
 469     count -= n;
 470     offset += n;
 471     blknum++;
 472   }
 473
 474   /* Aligned body */
 475   while (count >= BLOCKSIZE) {
 476     if (bitmap_get_blk (&bm, blknum, 0) != 0)
 477       goto unexpected_trim;
 478
 479     count -= BLOCKSIZE;
 480     offset += BLOCKSIZE;
 481     blknum++;
 482   }
 483
 484   /* Unaligned tail */
 485   if (count) {
 486     if (bitmap_get_blk (&bm, blknum, 0) != 0)
 487       goto unexpected_trim;
 488   }
 489
 490   return 0;
 491 }
 492
 493 static int
 494 sparse_random_extents (void *handle, uint32_t count, uint64_t offset,
 495                        uint32_t flags, struct nbdkit_extents *extents)
 496 {
 497   uint64_t blknum, blkoffs;
 498   uint32_t type;
 499
 500   blknum = offset / BLOCKSIZE;  /* block number */
 501   blkoffs = offset % BLOCKSIZE; /* offset within the block */
 502
 503   /* Unaligned head */
 504   if (blkoffs) {
 505     uint64_t n = MIN (BLOCKSIZE - blkoffs, count);
 506
 507     if (bitmap_get_blk (&bm, blknum, 0) == 0)
 508       type = NBDKIT_EXTENT_HOLE | NBDKIT_EXTENT_ZERO;
 509     else
 510       type = 0; /* data */
 511     if (nbdkit_add_extent (extents, offset, n, type) == -1)
 512       return -1;
 513
 514     count -= n;
 515     offset += n;
 516     blknum++;
 517   }
 518
 519   /* Aligned body */
 520   while (count >= BLOCKSIZE) {
 521     if (bitmap_get_blk (&bm, blknum, 0) == 0)
 522       type = NBDKIT_EXTENT_HOLE | NBDKIT_EXTENT_ZERO;
 523     else
 524       type = 0; /* data */
 525     if (nbdkit_add_extent (extents, offset, BLOCKSIZE, type) == -1)
 526       return -1;
 527
 528     count -= BLOCKSIZE;
 529     offset += BLOCKSIZE;
 530     blknum++;
 531   }
 532
 533   /* Unaligned tail */
 534   if (count) {
 535     if (bitmap_get_blk (&bm, blknum, 0) == 0)
 536       type = NBDKIT_EXTENT_HOLE | NBDKIT_EXTENT_ZERO;
 537     else
 538       type = 0; /* data */
 539     if (nbdkit_add_extent (extents, offset, count, type) == -1)
 540       return -1;
 541   }
 542
 543   return 0;
 544 }
 545
 546 static struct nbdkit_plugin plugin = {
 547   .name              = "sparse-random",
 548   .version           = PACKAGE_VERSION,
 549   .load              = sparse_random_load,
 550   .unload            = sparse_random_unload,
 551   .config            = sparse_random_config,
 552   .config_help       = sparse_random_config_help,
 553   .get_ready         = sparse_random_get_ready,
 554   .magic_config_key  = "size",
 555   .open              = sparse_random_open,
 556   .get_size          = sparse_random_get_size,
 557   .can_multi_conn    = sparse_random_can_multi_conn,
 558   .can_cache         = sparse_random_can_cache,
 559   .pread             = sparse_random_pread,
 560   .pwrite            = sparse_random_pwrite,
 561   .flush             = sparse_random_flush,
 562   .trim              = sparse_random_trim_zero,
 563   .zero              = sparse_random_trim_zero,
 564   .extents           = sparse_random_extents,
 565   /* In this plugin, errno is preserved properly along error return
 566    * paths from failed system calls.
 567    */
 568   .errno_is_preserved = 1,
 569 };
 570
 571 NBDKIT_REGISTER_PLUGIN (plugin)