lib/ntdb/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 <ccan/tally/tally.h>
  20
  21 #define SUMMARY_FORMAT \
  22         "Size of file/data: %zu/%zu\n" \
  23         "Number of records: %zu\n" \
  24         "Smallest/average/largest keys: %zu/%zu/%zu\n%s" \
  25         "Smallest/average/largest data: %zu/%zu/%zu\n%s" \
  26         "Smallest/average/largest padding: %zu/%zu/%zu\n%s" \
  27         "Number of free records: %zu\n" \
  28         "Smallest/average/largest free records: %zu/%zu/%zu\n%s" \
  29         "Number of uncoalesced records: %zu\n" \
  30         "Smallest/average/largest uncoalesced runs: %zu/%zu/%zu\n%s" \
  31         "Toplevel hash used: %u of %u\n" \
  32         "Number of hashes: %zu\n" \
  33         "Smallest/average/largest hash chains: %zu/%zu/%zu\n%s" \
  34         "Percentage keys/data/padding/free/rechdrs/freehdrs/hashes: %.0f/%.0f/%.0f/%.0f/%.0f/%.0f/%.0f\n"
  35
  36 #define BUCKET_SUMMARY_FORMAT_A                                 \
  37         "Free bucket %zu: total entries %zu.\n"                 \
  38         "Smallest/average/largest length: %zu/%zu/%zu\n%s"
  39 #define BUCKET_SUMMARY_FORMAT_B                                 \
  40         "Free bucket %zu-%zu: total entries %zu.\n"             \
  41         "Smallest/average/largest length: %zu/%zu/%zu\n%s"
  42 #define CAPABILITY_FORMAT                                       \
  43         "Capability %llu%s\n"
  44
  45 #define HISTO_WIDTH 70
  46 #define HISTO_HEIGHT 20
  47
  48 static ntdb_off_t count_hash(struct ntdb_context *ntdb,
  49                              ntdb_off_t hash_off,
  50                              ntdb_off_t num)
  51 {
  52         const ntdb_off_t *h;
  53         ntdb_off_t i, count = 0;
  54
  55         h = ntdb_access_read(ntdb, hash_off, sizeof(*h) * num, true);
  56         if (NTDB_PTR_IS_ERR(h)) {
  57                 return NTDB_ERR_TO_OFF(NTDB_PTR_ERR(h));
  58         }
  59         for (i = 0; i < num; i++)
  60                 count += (h[i] != 0);
  61
  62         ntdb_access_release(ntdb, h);
  63         return count;
  64 }
  65
  66 static enum NTDB_ERROR summarize(struct ntdb_context *ntdb,
  67                                 struct tally *ftables,
  68                                 struct tally *fr,
  69                                 struct tally *keys,
  70                                 struct tally *data,
  71                                 struct tally *extra,
  72                                 struct tally *uncoal,
  73                                 struct tally *hashes,
  74                                 size_t *num_caps)
  75 {
  76         ntdb_off_t off;
  77         ntdb_len_t len;
  78         ntdb_len_t unc = 0;
  79
  80         for (off = sizeof(struct ntdb_header);
  81              off < ntdb->file->map_size;
  82              off += len) {
  83                 const union {
  84                         struct ntdb_used_record u;
  85                         struct ntdb_free_record f;
  86                         struct ntdb_recovery_record r;
  87                 } *p;
  88                 /* We might not be able to get the whole thing. */
  89                 p = ntdb_access_read(ntdb, off, sizeof(p->f), true);
  90                 if (NTDB_PTR_IS_ERR(p)) {
  91                         return NTDB_PTR_ERR(p);
  92                 }
  93                 if (frec_magic(&p->f) != NTDB_FREE_MAGIC) {
  94                         if (unc > 1) {
  95                                 tally_add(uncoal, unc);
  96                                 unc = 0;
  97                         }
  98                 }
  99
 100                 if (p->r.magic == NTDB_RECOVERY_INVALID_MAGIC
 101                     || p->r.magic == NTDB_RECOVERY_MAGIC) {
 102                         len = sizeof(p->r) + p->r.max_len;
 103                 } else if (frec_magic(&p->f) == NTDB_FREE_MAGIC) {
 104                         len = frec_len(&p->f);
 105                         tally_add(fr, len);
 106                         len += sizeof(p->u);
 107                         unc++;
 108                 } else if (rec_magic(&p->u) == NTDB_USED_MAGIC) {
 109                         len = sizeof(p->u)
 110                                 + rec_key_length(&p->u)
 111                                 + rec_data_length(&p->u)
 112                                 + rec_extra_padding(&p->u);
 113
 114                         tally_add(keys, rec_key_length(&p->u));
 115                         tally_add(data, rec_data_length(&p->u));
 116                         tally_add(extra, rec_extra_padding(&p->u));
 117                 } else if (rec_magic(&p->u) == NTDB_HTABLE_MAGIC) {
 118                         ntdb_off_t count = count_hash(ntdb,
 119                                                       off + sizeof(p->u),
 120                                                       1 << ntdb->hash_bits);
 121                         if (NTDB_OFF_IS_ERR(count)) {
 122                                 return NTDB_OFF_TO_ERR(count);
 123                         }
 124                         tally_add(hashes, count);
 125                         tally_add(extra, rec_extra_padding(&p->u));
 126                         len = sizeof(p->u)
 127                                 + rec_data_length(&p->u)
 128                                 + rec_extra_padding(&p->u);
 129                 } else if (rec_magic(&p->u) == NTDB_FTABLE_MAGIC) {
 130                         len = sizeof(p->u)
 131                                 + rec_data_length(&p->u)
 132                                 + rec_extra_padding(&p->u);
 133                         tally_add(ftables, rec_data_length(&p->u));
 134                         tally_add(extra, rec_extra_padding(&p->u));
 135                 } else if (rec_magic(&p->u) == NTDB_CHAIN_MAGIC) {
 136                         len = sizeof(p->u)
 137                                 + rec_data_length(&p->u)
 138                                 + rec_extra_padding(&p->u);
 139                         tally_add(hashes,
 140                                   rec_data_length(&p->u)/sizeof(ntdb_off_t));
 141                         tally_add(extra, rec_extra_padding(&p->u));
 142                 } else if (rec_magic(&p->u) == NTDB_CAP_MAGIC) {
 143                         len = sizeof(p->u)
 144                                 + rec_data_length(&p->u)
 145                                 + rec_extra_padding(&p->u);
 146                         (*num_caps)++;
 147                 } else {
 148                         len = dead_space(ntdb, off);
 149                         if (NTDB_OFF_IS_ERR(len)) {
 150                                 return NTDB_OFF_TO_ERR(len);
 151                         }
 152                 }
 153                 ntdb_access_release(ntdb, p);
 154         }
 155         if (unc)
 156                 tally_add(uncoal, unc);
 157         return NTDB_SUCCESS;
 158 }
 159
 160 static void add_capabilities(struct ntdb_context *ntdb, char *summary)
 161 {
 162         ntdb_off_t off, next;
 163         const struct ntdb_capability *cap;
 164         size_t count = 0;
 165
 166         /* Append to summary. */
 167         summary += strlen(summary);
 168
 169         off = ntdb_read_off(ntdb, offsetof(struct ntdb_header, capabilities));
 170         if (NTDB_OFF_IS_ERR(off))
 171                 return;
 172
 173         /* Walk capability list. */
 174         for (; off; off = next) {
 175                 cap = ntdb_access_read(ntdb, off, sizeof(*cap), true);
 176                 if (NTDB_PTR_IS_ERR(cap)) {
 177                         break;
 178                 }
 179                 count++;
 180                 sprintf(summary, CAPABILITY_FORMAT,
 181                         cap->type & NTDB_CAP_TYPE_MASK,
 182                         /* Noopen?  How did we get here? */
 183                         (cap->type & NTDB_CAP_NOOPEN) ? " (unopenable)"
 184                         : ((cap->type & NTDB_CAP_NOWRITE)
 185                            && (cap->type & NTDB_CAP_NOCHECK)) ? " (uncheckable,read-only)"
 186                         : (cap->type & NTDB_CAP_NOWRITE) ? " (read-only)"
 187                         : (cap->type & NTDB_CAP_NOCHECK) ? " (uncheckable)"
 188                         : "");
 189                 summary += strlen(summary);
 190                 next = cap->next;
 191                 ntdb_access_release(ntdb, cap);
 192         }
 193 }
 194
 195 _PUBLIC_ enum NTDB_ERROR ntdb_summary(struct ntdb_context *ntdb,
 196                            enum ntdb_summary_flags flags,
 197                            char **summary)
 198 {
 199         ntdb_len_t len;
 200         size_t num_caps = 0;
 201         struct tally *ftables, *freet, *keys, *data, *extra, *uncoal, *hashes;
 202         char *freeg, *keysg, *datag, *extrag, *uncoalg, *hashesg;
 203         enum NTDB_ERROR ecode;
 204
 205         freeg = keysg = datag = extrag = uncoalg = hashesg = NULL;
 206
 207         ecode = ntdb_allrecord_lock(ntdb, F_RDLCK, NTDB_LOCK_WAIT, false);
 208         if (ecode != NTDB_SUCCESS) {
 209                 return ecode;
 210         }
 211
 212         ecode = ntdb_lock_expand(ntdb, F_RDLCK);
 213         if (ecode != NTDB_SUCCESS) {
 214                 ntdb_allrecord_unlock(ntdb, F_RDLCK);
 215                 return ecode;
 216         }
 217
 218         /* Start stats off empty. */
 219         ftables = tally_new(HISTO_HEIGHT);
 220         freet = tally_new(HISTO_HEIGHT);
 221         keys = tally_new(HISTO_HEIGHT);
 222         data = tally_new(HISTO_HEIGHT);
 223         extra = tally_new(HISTO_HEIGHT);
 224         uncoal = tally_new(HISTO_HEIGHT);
 225         hashes = tally_new(HISTO_HEIGHT);
 226         if (!ftables || !freet || !keys || !data || !extra
 227             || !uncoal || !hashes) {
 228                 ecode = ntdb_logerr(ntdb, NTDB_ERR_OOM, NTDB_LOG_ERROR,
 229                                    "ntdb_summary: failed to allocate"
 230                                    " tally structures");
 231                 goto unlock;
 232         }
 233
 234         ecode = summarize(ntdb, ftables, freet, keys, data, extra,
 235                           uncoal, hashes, &num_caps);
 236         if (ecode != NTDB_SUCCESS) {
 237                 goto unlock;
 238         }
 239
 240         if (flags & NTDB_SUMMARY_HISTOGRAMS) {
 241                 freeg = tally_histogram(freet, HISTO_WIDTH, HISTO_HEIGHT);
 242                 keysg = tally_histogram(keys, HISTO_WIDTH, HISTO_HEIGHT);
 243                 datag = tally_histogram(data, HISTO_WIDTH, HISTO_HEIGHT);
 244                 extrag = tally_histogram(extra, HISTO_WIDTH, HISTO_HEIGHT);
 245                 uncoalg = tally_histogram(uncoal, HISTO_WIDTH, HISTO_HEIGHT);
 246                 hashesg = tally_histogram(hashes, HISTO_WIDTH, HISTO_HEIGHT);
 247         }
 248
 249         /* 20 is max length of a %llu. */
 250         len = strlen(SUMMARY_FORMAT) + 33*20 + 1
 251                 + (freeg ? strlen(freeg) : 0)
 252                 + (keysg ? strlen(keysg) : 0)
 253                 + (datag ? strlen(datag) : 0)
 254                 + (extrag ? strlen(extrag) : 0)
 255                 + (uncoalg ? strlen(uncoalg) : 0)
 256                 + (hashesg ? strlen(hashesg) : 0)
 257                 + num_caps * (strlen(CAPABILITY_FORMAT) + 20
 258                               + strlen(" (uncheckable,read-only)"));
 259
 260         *summary = ntdb->alloc_fn(ntdb, len, ntdb->alloc_data);
 261         if (!*summary) {
 262                 ecode = ntdb_logerr(ntdb, NTDB_ERR_OOM, NTDB_LOG_ERROR,
 263                                    "ntdb_summary: failed to allocate string");
 264                 goto unlock;
 265         }
 266
 267         sprintf(*summary, SUMMARY_FORMAT,
 268                 (size_t)ntdb->file->map_size,
 269                 tally_total(keys, NULL) + tally_total(data, NULL),
 270                 tally_num(keys),
 271                 tally_min(keys), tally_mean(keys), tally_max(keys),
 272                 keysg ? keysg : "",
 273                 tally_min(data), tally_mean(data), tally_max(data),
 274                 datag ? datag : "",
 275                 tally_min(extra), tally_mean(extra), tally_max(extra),
 276                 extrag ? extrag : "",
 277                 tally_num(freet),
 278                 tally_min(freet), tally_mean(freet), tally_max(freet),
 279                 freeg ? freeg : "",
 280                 tally_total(uncoal, NULL),
 281                 tally_min(uncoal), tally_mean(uncoal), tally_max(uncoal),
 282                 uncoalg ? uncoalg : "",
 283                 (unsigned)count_hash(ntdb, sizeof(struct ntdb_header),
 284                                      1 << ntdb->hash_bits),
 285                 1 << ntdb->hash_bits,
 286                 tally_num(hashes),
 287                 tally_min(hashes), tally_mean(hashes), tally_max(hashes),
 288                 hashesg ? hashesg : "",
 289                 tally_total(keys, NULL) * 100.0 / ntdb->file->map_size,
 290                 tally_total(data, NULL) * 100.0 / ntdb->file->map_size,
 291                 tally_total(extra, NULL) * 100.0 / ntdb->file->map_size,
 292                 tally_total(freet, NULL) * 100.0 / ntdb->file->map_size,
 293                 (tally_num(keys) + tally_num(freet) + tally_num(hashes))
 294                 * sizeof(struct ntdb_used_record) * 100.0 / ntdb->file->map_size,
 295                 tally_num(ftables) * sizeof(struct ntdb_freetable)
 296                 * 100.0 / ntdb->file->map_size,
 297                 (tally_total(hashes, NULL) * sizeof(ntdb_off_t)
 298                  + (sizeof(ntdb_off_t) << ntdb->hash_bits))
 299                 * 100.0 / ntdb->file->map_size);
 300
 301         add_capabilities(ntdb, *summary);
 302
 303 unlock:
 304         ntdb->free_fn(freeg, ntdb->alloc_data);
 305         ntdb->free_fn(keysg, ntdb->alloc_data);
 306         ntdb->free_fn(datag, ntdb->alloc_data);
 307         ntdb->free_fn(extrag, ntdb->alloc_data);
 308         ntdb->free_fn(uncoalg, ntdb->alloc_data);
 309         ntdb->free_fn(hashesg, ntdb->alloc_data);
 310         ntdb->free_fn(freet, ntdb->alloc_data);
 311         ntdb->free_fn(keys, ntdb->alloc_data);
 312         ntdb->free_fn(data, ntdb->alloc_data);
 313         ntdb->free_fn(extra, ntdb->alloc_data);
 314         ntdb->free_fn(uncoal, ntdb->alloc_data);
 315         ntdb->free_fn(ftables, ntdb->alloc_data);
 316         ntdb->free_fn(hashes, ntdb->alloc_data);
 317
 318         ntdb_allrecord_unlock(ntdb, F_RDLCK);
 319         ntdb_unlock_expand(ntdb, F_RDLCK);
 320         return ecode;
 321 }