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 __FBSDID("$FreeBSD$");
  29
  30 #include <err.h>
  31 #include <stdio.h>
  32 #include <stdlib.h>
  33 #include <string.h>
  34 #include <unistd.h>
  35
  36 #if defined(MKUZ_DEBUG)
  37 # include <assert.h>
  38 # include <stdio.h>
  39 #endif
  40
  41 #include "mkuz_blockcache.h"
  42 #include "mkuz_blk.h"
  43
  44 struct mkuz_blkcache_itm {
  45     struct mkuz_blk_info hit;
  46     struct mkuz_blkcache_itm *next;
  47 };
  48
  49 static struct mkuz_blkcache {
  50     struct mkuz_blkcache_itm first[256];
  51 } blkcache;
  52
  53 static int
  54 verify_match(int fd, const struct mkuz_blk *cbp, struct mkuz_blkcache_itm *bcep)
  55 {
  56     void *vbuf;
  57     ssize_t rlen;
  58     int rval;
  59
  60     rval = -1;
  61     vbuf = malloc(cbp->info.len);
  62     if (vbuf == NULL) {
  63         goto e0;
  64     }
  65     if (lseek(fd, bcep->hit.offset, SEEK_SET) < 0) {
  66         goto e1;
  67     }
  68     rlen = read(fd, vbuf, cbp->info.len);
  69     if (rlen < 0 || (unsigned)rlen != cbp->info.len) {
  70         goto e2;
  71     }
  72     rval = (memcmp(cbp->data, vbuf, cbp->info.len) == 0) ? 1 : 0;
  73 e2:
  74     lseek(fd, cbp->info.offset, SEEK_SET);
  75 e1:
  76     free(vbuf);
  77 e0:
  78     return (rval);
  79 }
  80
  81 #define I2J(x)  ((intmax_t)(x))
  82 #define U2J(x)  ((uintmax_t)(x))
  83
  84 static unsigned char
  85 digest_fold(const unsigned char *mdigest)
  86 {
  87     int i;
  88     unsigned char rval;
  89
  90     rval = mdigest[0];
  91     for (i = 1; i < 16; i++) {
  92         rval = rval ^ mdigest[i];
  93     }
  94     return (rval);
  95 }
  96
  97 struct mkuz_blk_info *
  98 mkuz_blkcache_regblock(int fd, const struct mkuz_blk *bp)
  99 {
 100     struct mkuz_blkcache_itm *bcep;
 101     int rval;
 102     unsigned char h;
 103
 104 #if defined(MKUZ_DEBUG)
 105     assert((unsigned)lseek(fd, 0, SEEK_CUR) == bp->info.offset);
 106 #endif
 107     h = digest_fold(bp->info.digest);
 108     if (blkcache.first[h].hit.len == 0) {
 109         bcep = &blkcache.first[h];
 110     } else {
 111         for (bcep = &blkcache.first[h]; bcep != NULL; bcep = bcep->next) {
 112             if (bcep->hit.len != bp->info.len)
 113                 continue;
 114             if (memcmp(bp->info.digest, bcep->hit.digest,
 115               sizeof(bp->info.digest)) == 0) {
 116                 break;
 117             }
 118         }
 119         if (bcep != NULL) {
 120             rval = verify_match(fd, bp, bcep);
 121             if (rval == 1) {
 122 #if defined(MKUZ_DEBUG)
 123                 fprintf(stderr, "cache hit %jd, %jd, %jd, %jd\n",
 124                   I2J(bcep->hit.blkno), I2J(bcep->hit.offset),
 125                   I2J(bp->info.offset), I2J(bp->info.len));
 126 #endif
 127                 return (&bcep->hit);
 128             }
 129             if (rval == 0) {
 130 #if defined(MKUZ_DEBUG)
 131                 fprintf(stderr, "block MD5 collision, you should try lottery, "
 132                   "man!\n");
 133 #endif
 134                 return (NULL);
 135             }
 136             warn("verify_match");
 137             return (NULL);
 138         }
 139         bcep = malloc(sizeof(struct mkuz_blkcache_itm));
 140         if (bcep == NULL)
 141             return (NULL);
 142         memset(bcep, '\0', sizeof(struct mkuz_blkcache_itm));
 143         bcep->next = blkcache.first[h].next;
 144         blkcache.first[h].next = bcep;
 145     }
 146     bcep->hit = bp->info;
 147     return (NULL);
 148 }