usr.bin/mkuzip/mkuz_blockcache.c

   1 /*
   2  * Copyright (c) 2016 Maxim Sobolev <sobomax@FreeBSD.org>
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  24  * SUCH DAMAGE.
  25  */
  26
  27 #include <sys/cdefs.h>
  28 #include <err.h>
  29 #include <stdio.h>
  30 #include <stdlib.h>
  31 #include <string.h>
  32 #include <unistd.h>
  33
  34 #if defined(MKUZ_DEBUG)
  35 # include <assert.h>
  36 # include <stdio.h>
  37 #endif
  38
  39 #include "mkuz_blockcache.h"
  40 #include "mkuz_blk.h"
  41
  42 struct mkuz_blkcache_itm {
  43     struct mkuz_blk_info hit;
  44     struct mkuz_blkcache_itm *next;
  45 };
  46
  47 static struct mkuz_blkcache {
  48     struct mkuz_blkcache_itm first[256];
  49 } blkcache;
  50
  51 static int
  52 verify_match(int fd, const struct mkuz_blk *cbp, struct mkuz_blkcache_itm *bcep)
  53 {
  54     void *vbuf;
  55     ssize_t rlen;
  56     int rval;
  57
  58     rval = -1;
  59     vbuf = malloc(cbp->info.len);
  60     if (vbuf == NULL) {
  61         goto e0;
  62     }
  63     if (lseek(fd, bcep->hit.offset, SEEK_SET) < 0) {
  64         goto e1;
  65     }
  66     rlen = read(fd, vbuf, cbp->info.len);
  67     if (rlen < 0 || (unsigned)rlen != cbp->info.len) {
  68         goto e2;
  69     }
  70     rval = (memcmp(cbp->data, vbuf, cbp->info.len) == 0) ? 1 : 0;
  71 e2:
  72     lseek(fd, cbp->info.offset, SEEK_SET);
  73 e1:
  74     free(vbuf);
  75 e0:
  76     return (rval);
  77 }
  78
  79 #define I2J(x)  ((intmax_t)(x))
  80 #define U2J(x)  ((uintmax_t)(x))
  81
  82 static unsigned char
  83 digest_fold(const unsigned char *mdigest)
  84 {
  85     int i;
  86     unsigned char rval;
  87
  88     rval = mdigest[0];
  89     for (i = 1; i < 16; i++) {
  90         rval = rval ^ mdigest[i];
  91     }
  92     return (rval);
  93 }
  94
  95 struct mkuz_blk_info *
  96 mkuz_blkcache_regblock(int fd, const struct mkuz_blk *bp)
  97 {
  98     struct mkuz_blkcache_itm *bcep;
  99     int rval;
 100     unsigned char h;
 101
 102 #if defined(MKUZ_DEBUG)
 103     assert((unsigned)lseek(fd, 0, SEEK_CUR) == bp->info.offset);
 104 #endif
 105     h = digest_fold(bp->info.digest);
 106     if (blkcache.first[h].hit.len == 0) {
 107         bcep = &blkcache.first[h];
 108     } else {
 109         for (bcep = &blkcache.first[h]; bcep != NULL; bcep = bcep->next) {
 110             if (bcep->hit.len != bp->info.len)
 111                 continue;
 112             if (memcmp(bp->info.digest, bcep->hit.digest,
 113               sizeof(bp->info.digest)) == 0) {
 114                 break;
 115             }
 116         }
 117         if (bcep != NULL) {
 118             rval = verify_match(fd, bp, bcep);
 119             if (rval == 1) {
 120 #if defined(MKUZ_DEBUG)
 121                 fprintf(stderr, "cache hit %jd, %jd, %jd, %jd\n",
 122                   I2J(bcep->hit.blkno), I2J(bcep->hit.offset),
 123                   I2J(bp->info.offset), I2J(bp->info.len));
 124 #endif
 125                 return (&bcep->hit);
 126             }
 127             if (rval == 0) {
 128 #if defined(MKUZ_DEBUG)
 129                 fprintf(stderr, "block MD5 collision, you should try lottery, "
 130                   "man!\n");
 131 #endif
 132                 return (NULL);
 133             }
 134             warn("verify_match");
 135             return (NULL);
 136         }
 137         bcep = malloc(sizeof(struct mkuz_blkcache_itm));
 138         if (bcep == NULL)
 139             return (NULL);
 140         memset(bcep, '\0', sizeof(struct mkuz_blkcache_itm));
 141         bcep->next = blkcache.first[h].next;
 142         blkcache.first[h].next = bcep;
 143     }
 144     bcep->hit = bp->info;
 145     return (NULL);
 146 }