git.ozlabs.org Git - ccan/blob - ccan/tdb2/summary.c

   1  /*
   2    Trivial Database 2: human-readable summary code
   3    Copyright (C) Rusty Russell 2010
   4
   5    This library is free software; you can redistribute it and/or
   6    modify it under the terms of the GNU Lesser General Public
   7    License as published by the Free Software Foundation; either
   8    version 3 of the License, or (at your option) any later version.
   9
  10    This library is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13    Lesser General Public License for more details.
  14
  15    You should have received a copy of the GNU Lesser General Public
  16    License along with this library; if not, see <http://www.gnu.org/licenses/>.
  17 */
  18 #include "private.h"
  19 #include <assert.h>
  20 #include <ccan/tally/tally.h>
  21
  22 static int count_hash(struct tdb_context *tdb,
  23                       tdb_off_t hash_off, unsigned bits)
  24 {
  25         const tdb_off_t *h;
  26         unsigned int i, count = 0;
  27
  28         h = tdb_access_read(tdb, hash_off, sizeof(*h) << bits, true);
  29         if (!h)
  30                 return -1;
  31         for (i = 0; i < (1 << bits); i++)
  32                 count += (h[i] != 0);
  33
  34         tdb_access_release(tdb, h);
  35         return count;
  36 }
  37
  38 static bool summarize(struct tdb_context *tdb,
  39                       struct tally *hashes,
  40                       struct tally *ftables,
  41                       struct tally *fr,
  42                       struct tally *keys,
  43                       struct tally *data,
  44                       struct tally *extra,
  45                       struct tally *uncoal,
  46                       struct tally *buckets,
  47                       struct tally *chains)
  48 {
  49         tdb_off_t off;
  50         tdb_len_t len;
  51         tdb_len_t unc = 0;
  52
  53         for (off = sizeof(struct tdb_header); off < tdb->map_size; off += len) {
  54                 const union {
  55                         struct tdb_used_record u;
  56                         struct tdb_free_record f;
  57                         struct tdb_recovery_record r;
  58                 } *p;
  59                 /* We might not be able to get the whole thing. */
  60                 p = tdb_access_read(tdb, off, sizeof(p->f), true);
  61                 if (!p)
  62                         return false;
  63                 if (p->r.magic == TDB_RECOVERY_INVALID_MAGIC
  64                     || p->r.magic == TDB_RECOVERY_MAGIC) {
  65                         if (unc) {
  66                                 tally_add(uncoal, unc);
  67                                 unc = 0;
  68                         }
  69                         len = sizeof(p->r) + p->r.max_len;
  70                 } else if (frec_magic(&p->f) == TDB_FREE_MAGIC) {
  71                         len = frec_len(&p->f);
  72                         tally_add(fr, len);
  73                         tally_add(buckets, size_to_bucket(len));
  74                         len += sizeof(p->u);
  75                         unc++;
  76                 } else if (rec_magic(&p->u) == TDB_USED_MAGIC) {
  77                         if (unc) {
  78                                 tally_add(uncoal, unc);
  79                                 unc = 0;
  80                         }
  81                         len = sizeof(p->u)
  82                                 + rec_key_length(&p->u)
  83                                 + rec_data_length(&p->u)
  84                                 + rec_extra_padding(&p->u);
  85
  86                         tally_add(keys, rec_key_length(&p->u));
  87                         tally_add(data, rec_data_length(&p->u));
  88                         tally_add(extra, rec_extra_padding(&p->u));
  89                 } else if (rec_magic(&p->u) == TDB_HTABLE_MAGIC) {
  90                         int count = count_hash(tdb,
  91                                                off + sizeof(p->u),
  92                                                TDB_SUBLEVEL_HASH_BITS);
  93                         if (count == -1)
  94                                 return false;
  95                         tally_add(hashes, count);
  96                         tally_add(extra, rec_extra_padding(&p->u));
  97                         len = sizeof(p->u)
  98                                 + rec_data_length(&p->u)
  99                                 + rec_extra_padding(&p->u);
 100                 } else if (rec_magic(&p->u) == TDB_FTABLE_MAGIC) {
 101                         len = sizeof(p->u)
 102                                 + rec_data_length(&p->u)
 103                                 + rec_extra_padding(&p->u);
 104                         tally_add(ftables, rec_data_length(&p->u));
 105                         tally_add(extra, rec_extra_padding(&p->u));
 106                 } else if (rec_magic(&p->u) == TDB_CHAIN_MAGIC) {
 107                         len = sizeof(p->u)
 108                                 + rec_data_length(&p->u)
 109                                 + rec_extra_padding(&p->u);
 110                         tally_add(chains, 1);
 111                         tally_add(extra, rec_extra_padding(&p->u));
 112                 } else
 113                         len = dead_space(tdb, off);
 114                 tdb_access_release(tdb, p);
 115         }
 116         if (unc)
 117                 tally_add(uncoal, unc);
 118         return true;
 119 }
 120
 121 #define SUMMARY_FORMAT \
 122         "Size of file/data: %zu/%zu\n" \
 123         "Number of records: %zu\n" \
 124         "Smallest/average/largest keys: %zu/%zu/%zu\n%s" \
 125         "Smallest/average/largest data: %zu/%zu/%zu\n%s" \
 126         "Smallest/average/largest padding: %zu/%zu/%zu\n%s" \
 127         "Number of free records: %zu\n" \
 128         "Smallest/average/largest free records: %zu/%zu/%zu\n%s" \
 129         "Number of uncoalesced records: %zu\n" \
 130         "Smallest/average/largest uncoalesced runs: %zu/%zu/%zu\n%s" \
 131         "Number of free lists: %zu\n%s" \
 132         "Toplevel hash used: %u of %u\n" \
 133         "Number of chains: %zu\n" \
 134         "Number of subhashes: %zu\n" \
 135         "Smallest/average/largest subhash entries: %zu/%zu/%zu\n%s" \
 136         "Percentage keys/data/padding/free/rechdrs/freehdrs/hashes: %.0f/%.0f/%.0f/%.0f/%.0f/%.0f/%.0f\n"
 137
 138 #define BUCKET_SUMMARY_FORMAT_A                                 \
 139         "Free bucket %zu: total entries %zu.\n"                 \
 140         "Smallest/average/largest length: %zu/%zu/%zu\n%s"
 141 #define BUCKET_SUMMARY_FORMAT_B                                 \
 142         "Free bucket %zu-%zu: total entries %zu.\n"             \
 143         "Smallest/average/largest length: %zu/%zu/%zu\n%s"
 144
 145 #define HISTO_WIDTH 70
 146 #define HISTO_HEIGHT 20
 147
 148 char *tdb_summary(struct tdb_context *tdb, enum tdb_summary_flags flags)
 149 {
 150         tdb_len_t len;
 151         struct tally *ftables, *hashes, *freet, *keys, *data, *extra, *uncoal,
 152                 *buckets, *chains;
 153         char *hashesg, *freeg, *keysg, *datag, *extrag, *uncoalg, *bucketsg;
 154         char *ret = NULL;
 155
 156         hashesg = freeg = keysg = datag = extrag = uncoalg = bucketsg = NULL;
 157
 158         if (tdb_allrecord_lock(tdb, F_RDLCK, TDB_LOCK_WAIT, false) != 0)
 159                 return NULL;
 160
 161         if (tdb_lock_expand(tdb, F_RDLCK) != 0) {
 162                 tdb_allrecord_unlock(tdb, F_RDLCK);
 163                 return NULL;
 164         }
 165
 166         /* Start stats off empty. */
 167         ftables = tally_new(HISTO_HEIGHT);
 168         hashes = tally_new(HISTO_HEIGHT);
 169         freet = tally_new(HISTO_HEIGHT);
 170         keys = tally_new(HISTO_HEIGHT);
 171         data = tally_new(HISTO_HEIGHT);
 172         extra = tally_new(HISTO_HEIGHT);
 173         uncoal = tally_new(HISTO_HEIGHT);
 174         buckets = tally_new(HISTO_HEIGHT);
 175         chains = tally_new(HISTO_HEIGHT);
 176         if (!ftables || !hashes || !freet || !keys || !data || !extra
 177             || !uncoal || !buckets || !chains) {
 178                 tdb_logerr(tdb, TDB_ERR_OOM, TDB_LOG_ERROR,
 179                            "tdb_summary: failed to allocate tally structures");
 180                 goto unlock;
 181         }
 182
 183         if (!summarize(tdb, hashes, ftables, freet, keys, data, extra, uncoal,
 184                        buckets, chains))
 185                 goto unlock;
 186
 187         if (flags & TDB_SUMMARY_HISTOGRAMS) {
 188                 hashesg = tally_histogram(hashes, HISTO_WIDTH, HISTO_HEIGHT);
 189                 freeg = tally_histogram(freet, HISTO_WIDTH, HISTO_HEIGHT);
 190                 keysg = tally_histogram(keys, HISTO_WIDTH, HISTO_HEIGHT);
 191                 datag = tally_histogram(data, HISTO_WIDTH, HISTO_HEIGHT);
 192                 extrag = tally_histogram(extra, HISTO_WIDTH, HISTO_HEIGHT);
 193                 uncoalg = tally_histogram(uncoal, HISTO_WIDTH, HISTO_HEIGHT);
 194                 bucketsg = tally_histogram(buckets, HISTO_WIDTH, HISTO_HEIGHT);
 195         }
 196
 197         /* 20 is max length of a %llu. */
 198         len = strlen(SUMMARY_FORMAT) + 33*20 + 1
 199                 + (hashesg ? strlen(hashesg) : 0)
 200                 + (freeg ? strlen(freeg) : 0)
 201                 + (keysg ? strlen(keysg) : 0)
 202                 + (datag ? strlen(datag) : 0)
 203                 + (extrag ? strlen(extrag) : 0)
 204                 + (uncoalg ? strlen(uncoalg) : 0)
 205                 + (bucketsg ? strlen(bucketsg) : 0);
 206
 207         ret = malloc(len);
 208         if (!ret)
 209                 goto unlock;
 210
 211         len = sprintf(ret, SUMMARY_FORMAT,
 212                       (size_t)tdb->map_size,
 213                       tally_num(keys) + tally_num(data),
 214                       tally_num(keys),
 215                       tally_min(keys), tally_mean(keys), tally_max(keys),
 216                       keysg ? keysg : "",
 217                       tally_min(data), tally_mean(data), tally_max(data),
 218                       datag ? datag : "",
 219                       tally_min(extra), tally_mean(extra), tally_max(extra),
 220                       extrag ? extrag : "",
 221                       tally_num(freet),
 222                       tally_min(freet), tally_mean(freet), tally_max(freet),
 223                       freeg ? freeg : "",
 224                       tally_total(uncoal, NULL),
 225                       tally_min(uncoal), tally_mean(uncoal), tally_max(uncoal),
 226                       uncoalg ? uncoalg : "",
 227                       tally_num(buckets),
 228                       bucketsg ? bucketsg : "",
 229                       count_hash(tdb, offsetof(struct tdb_header, hashtable),
 230                                  TDB_TOPLEVEL_HASH_BITS),
 231                       1 << TDB_TOPLEVEL_HASH_BITS,
 232                       tally_num(chains),
 233                       tally_num(hashes),
 234                       tally_min(hashes), tally_mean(hashes), tally_max(hashes),
 235                       hashesg ? hashesg : "",
 236                       tally_total(keys, NULL) * 100.0 / tdb->map_size,
 237                       tally_total(data, NULL) * 100.0 / tdb->map_size,
 238                       tally_total(extra, NULL) * 100.0 / tdb->map_size,
 239                       tally_total(freet, NULL) * 100.0 / tdb->map_size,
 240                       (tally_num(keys) + tally_num(freet) + tally_num(hashes))
 241                       * sizeof(struct tdb_used_record) * 100.0 / tdb->map_size,
 242                       tally_num(ftables) * sizeof(struct tdb_freetable)
 243                       * 100.0 / tdb->map_size,
 244                       (tally_num(hashes)
 245                        * (sizeof(tdb_off_t) << TDB_SUBLEVEL_HASH_BITS)
 246                        + (sizeof(tdb_off_t) << TDB_TOPLEVEL_HASH_BITS)
 247                        + sizeof(struct tdb_chain) * tally_num(chains))
 248                       * 100.0 / tdb->map_size);
 249
 250 unlock:
 251         free(hashesg);
 252         free(freeg);
 253         free(keysg);
 254         free(datag);
 255         free(extrag);
 256         free(uncoalg);
 257         free(bucketsg);
 258         free(hashes);
 259         free(buckets);
 260         free(freet);
 261         free(keys);
 262         free(data);
 263         free(extra);
 264         free(uncoal);
 265         free(ftables);
 266         free(chains);
 267
 268         tdb_allrecord_unlock(tdb, F_RDLCK);
 269         tdb_unlock_expand(tdb, F_RDLCK);
 270         return ret;
 271 }