egg/egg-secure-memory.c

   1 /* -*- Mode: C; indent-tabs-mode: t; c-basic-offset: 8; tab-width: 8 -*- */
   2 /* egg-secure-memory.h - library for allocating memory that is non-pageable
   3
   4    Copyright (C) 2007 Stefan Walter
   5
   6    The Gnome Keyring Library is free software; you can redistribute it and/or
   7    modify it under the terms of the GNU Library General Public License as
   8    published by the Free Software Foundation; either version 2 of the
   9    License, or (at your option) any later version.
  10
  11    The Gnome Keyring Library is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14    Library General Public License for more details.
  15
  16    You should have received a copy of the GNU Library General Public
  17    License along with the Gnome Library; see the file COPYING.LIB.  If not,
  18    see <http://www.gnu.org/licenses/>.
  19
  20    Author: Stef Walter <stef@memberwebs.com>
  21 */
  22
  23 /*
  24  * IMPORTANT: This is pure vanila standard C, no glib. We need this
  25  * because certain consumers of this protocol need to be built
  26  * without linking in any special libraries. ie: the PKCS#11 module.
  27  */
  28
  29 #include "config.h"
  30
  31 #include "egg-secure-memory.h"
  32
  33 #include <sys/types.h>
  34 #include <sys/mman.h>
  35 #include <stddef.h>
  36 #include <string.h>
  37 #include <stdio.h>
  38 #include <stdlib.h>
  39 #include <errno.h>
  40 #include <unistd.h>
  41 #include <assert.h>
  42
  43 #ifdef WITH_VALGRIND
  44 #include <valgrind/valgrind.h>
  45 #include <valgrind/memcheck.h>
  46 #endif
  47
  48 #define DEBUG_SECURE_MEMORY 0
  49
  50 #if DEBUG_SECURE_MEMORY
  51 #define DEBUG_ALLOC(msg, n)     fprintf(stderr, "%s %lu bytes\n", msg, n);
  52 #else
  53 #define DEBUG_ALLOC(msg, n)
  54 #endif
  55
  56 #define DEFAULT_BLOCK_SIZE 16384
  57
  58 /* Use our own assert to guarantee no glib allocations */
  59 #ifndef ASSERT
  60 #ifdef G_DISABLE_ASSERT
  61 #define ASSERT(x)
  62 #else
  63 #define ASSERT(x) assert(x)
  64 #endif
  65 #endif
  66
  67 #define DO_LOCK() \
  68         EGG_SECURE_GLOBALS.lock ();
  69
  70 #define DO_UNLOCK() \
  71         EGG_SECURE_GLOBALS.unlock ();
  72
  73 static int show_warning = 1;
  74 int egg_secure_warnings = 1;
  75
  76 /*
  77  * We allocate all memory in units of sizeof(void*). This
  78  * is our definition of 'word'.
  79  */
  80 typedef void* word_t;
  81
  82 /* The amount of extra words we can allocate */
  83 #define WASTE   4
  84
  85 /*
  86  * Track allocated memory or a free block. This structure is not stored
  87  * in the secure memory area. It is allocated from a pool of other
  88  * memory. See meta_pool_xxx ().
  89  */
  90 typedef struct _Cell {
  91         word_t *words;          /* Pointer to secure memory */
  92         size_t n_words;         /* Amount of secure memory in words */
  93         size_t requested;       /* Amount actually requested by app, in bytes, 0 if unused */
  94         const char *tag;        /* Tag which describes the allocation */
  95         struct _Cell *next;     /* Next in memory ring */
  96         struct _Cell *prev;     /* Previous in memory ring */
  97 } Cell;
  98
  99 /*
 100  * A block of secure memory. This structure is the header in that block.
 101  */
 102 typedef struct _Block {
 103         word_t *words;              /* Actual memory hangs off here */
 104         size_t n_words;             /* Number of words in block */
 105         size_t n_used;              /* Number of used allocations */
 106         struct _Cell* used_cells;   /* Ring of used allocations */
 107         struct _Cell* unused_cells; /* Ring of unused allocations */
 108         struct _Block *next;        /* Next block in list */
 109 } Block;
 110
 111 /* -----------------------------------------------------------------------------
 112  * UNUSED STACK
 113  */
 114
 115 static inline void
 116 unused_push (void **stack, void *ptr)
 117 {
 118         ASSERT (ptr);
 119         ASSERT (stack);
 120         *((void**)ptr) = *stack;
 121         *stack = ptr;
 122 }
 123
 124 static inline void*
 125 unused_pop (void **stack)
 126 {
 127         void *ptr;
 128         ASSERT (stack);
 129         ptr = *stack;
 130         *stack = *(void**)ptr;
 131         return ptr;
 132
 133 }
 134
 135 static inline void*
 136 unused_peek (void **stack)
 137 {
 138         ASSERT (stack);
 139         return *stack;
 140 }
 141
 142 /* -----------------------------------------------------------------------------
 143  * POOL META DATA ALLOCATION
 144  *
 145  * A pool for memory meta data. We allocate fixed size blocks. There are actually
 146  * two different structures stored in this pool: Cell and Block. Cell is allocated
 147  * way more often, and is bigger so we just allocate that size for both.
 148  */
 149
 150 /* Pool allocates this data type */
 151 typedef union _Item {
 152                 Cell cell;
 153                 Block block;
 154 } Item;
 155
 156 typedef struct _Pool {
 157         struct _Pool *next;    /* Next pool in list */
 158         size_t length;         /* Length in bytes of the pool */
 159         size_t used;           /* Number of cells used in pool */
 160         void *unused;          /* Unused stack of unused stuff */
 161         size_t n_items;        /* Total number of items in pool */
 162         Item items[1];         /* Actual items hang off here */
 163 } Pool;
 164
 165 static void *
 166 pool_alloc (void)
 167 {
 168         Pool *pool;
 169         void *pages, *item;
 170         size_t len, i;
 171
 172         if (!EGG_SECURE_GLOBALS.pool_version ||
 173             strcmp (EGG_SECURE_GLOBALS.pool_version, EGG_SECURE_POOL_VER_STR) != 0) {
 174                 if (show_warning && egg_secure_warnings)
 175                         fprintf (stderr, "the secure memory pool version does not match the code '%s' != '%s'\n",
 176                                  EGG_SECURE_GLOBALS.pool_version ? EGG_SECURE_GLOBALS.pool_version : "(null)",
 177                                  EGG_SECURE_POOL_VER_STR);
 178                 show_warning = 0;
 179                 return NULL;
 180         }
 181
 182         /* A pool with an available item */
 183         for (pool = EGG_SECURE_GLOBALS.pool_data; pool; pool = pool->next) {
 184                 if (unused_peek (&pool->unused))
 185                         break;
 186         }
 187
 188         /* Create a new pool */
 189         if (pool == NULL) {
 190                 len = getpagesize () * 2;
 191                 pages = mmap (0, len, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, -1, 0);
 192                 if (pages == MAP_FAILED)
 193                         return NULL;
 194
 195                 /* Fill in the block header, and inlude in block list */
 196                 pool = pages;
 197                 pool->next = EGG_SECURE_GLOBALS.pool_data;
 198                 EGG_SECURE_GLOBALS.pool_data = pool;
 199                 pool->length = len;
 200                 pool->used = 0;
 201                 pool->unused = NULL;
 202
 203                 /* Fill block with unused items */
 204                 pool->n_items = (len - sizeof (Pool)) / sizeof (Item);
 205                 for (i = 0; i < pool->n_items; ++i)
 206                         unused_push (&pool->unused, pool->items + i);
 207
 208 #ifdef WITH_VALGRIND
 209                 VALGRIND_CREATE_MEMPOOL(pool, 0, 0);
 210 #endif
 211         }
 212
 213         ++pool->used;
 214         ASSERT (unused_peek (&pool->unused));
 215         item = unused_pop (&pool->unused);
 216
 217 #ifdef WITH_VALGRIND
 218         VALGRIND_MEMPOOL_ALLOC (pool, item, sizeof (Item));
 219 #endif
 220
 221         return memset (item, 0, sizeof (Item));
 222 }
 223
 224 static void
 225 pool_free (void* item)
 226 {
 227         Pool *pool, **at;
 228         char *ptr, *beg, *end;
 229
 230         ptr = item;
 231
 232         /* Find which block this one belongs to */
 233         for (at = (Pool **)&EGG_SECURE_GLOBALS.pool_data, pool = *at;
 234              pool != NULL; at = &pool->next, pool = *at) {
 235                 beg = (char*)pool->items;
 236                 end = (char*)pool + pool->length - sizeof (Item);
 237                 if (ptr >= beg && ptr <= end) {
 238                         ASSERT ((ptr - beg) % sizeof (Item) == 0);
 239                         break;
 240                 }
 241         }
 242
 243         /* Otherwise invalid meta */
 244         ASSERT (at);
 245         ASSERT (pool);
 246         ASSERT (pool->used > 0);
 247
 248         /* No more meta cells used in this block, remove from list, destroy */
 249         if (pool->used == 1) {
 250                 *at = pool->next;
 251
 252 #ifdef WITH_VALGRIND
 253                 VALGRIND_DESTROY_MEMPOOL (pool);
 254 #endif
 255
 256                 munmap (pool, pool->length);
 257                 return;
 258         }
 259
 260 #ifdef WITH_VALGRIND
 261         VALGRIND_MEMPOOL_FREE (pool, item);
 262         VALGRIND_MAKE_MEM_UNDEFINED (item, sizeof (Item));
 263 #endif
 264
 265         --pool->used;
 266         memset (item, 0xCD, sizeof (Item));
 267         unused_push (&pool->unused, item);
 268 }
 269
 270 #ifndef G_DISABLE_ASSERT
 271
 272 static int
 273 pool_valid (void* item)
 274 {
 275         Pool *pool;
 276         char *ptr, *beg, *end;
 277
 278         ptr = item;
 279
 280         /* Find which block this one belongs to */
 281         for (pool = EGG_SECURE_GLOBALS.pool_data; pool; pool = pool->next) {
 282                 beg = (char*)pool->items;
 283                 end = (char*)pool + pool->length - sizeof (Item);
 284                 if (ptr >= beg && ptr <= end)
 285                         return (pool->used && (ptr - beg) % sizeof (Item) == 0);
 286         }
 287
 288         return 0;
 289 }
 290
 291 #endif /* G_DISABLE_ASSERT */
 292
 293 /* -----------------------------------------------------------------------------
 294  * SEC ALLOCATION
 295  *
 296  * Each memory cell begins and ends with a pointer to its metadata. These are also
 297  * used as guards or red zones. Since they're treated as redzones by valgrind we
 298  * have to jump through a few hoops before reading and/or writing them.
 299  */
 300
 301 static inline size_t
 302 sec_size_to_words (size_t length)
 303 {
 304         return (length % sizeof (void*) ? 1 : 0) + (length / sizeof (void*));
 305 }
 306
 307 static inline void
 308 sec_write_guards (Cell *cell)
 309 {
 310 #ifdef WITH_VALGRIND
 311         VALGRIND_MAKE_MEM_UNDEFINED (cell->words, sizeof (word_t));
 312         VALGRIND_MAKE_MEM_UNDEFINED (cell->words + cell->n_words - 1, sizeof (word_t));
 313 #endif
 314
 315         ((void**)cell->words)[0] = (void*)cell;
 316         ((void**)cell->words)[cell->n_words - 1] = (void*)cell;
 317
 318 #ifdef WITH_VALGRIND
 319         VALGRIND_MAKE_MEM_NOACCESS (cell->words, sizeof (word_t));
 320         VALGRIND_MAKE_MEM_NOACCESS (cell->words + cell->n_words - 1, sizeof (word_t));
 321 #endif
 322 }
 323
 324 static inline void
 325 sec_check_guards (Cell *cell)
 326 {
 327 #ifdef WITH_VALGRIND
 328         VALGRIND_MAKE_MEM_DEFINED (cell->words, sizeof (word_t));
 329         VALGRIND_MAKE_MEM_DEFINED (cell->words + cell->n_words - 1, sizeof (word_t));
 330 #endif
 331
 332         ASSERT(((void**)cell->words)[0] == (void*)cell);
 333         ASSERT(((void**)cell->words)[cell->n_words - 1] == (void*)cell);
 334
 335 #ifdef WITH_VALGRIND
 336         VALGRIND_MAKE_MEM_NOACCESS (cell->words, sizeof (word_t));
 337         VALGRIND_MAKE_MEM_NOACCESS (cell->words + cell->n_words - 1, sizeof (word_t));
 338 #endif
 339 }
 340
 341 static void
 342 sec_insert_cell_ring (Cell **ring, Cell *cell)
 343 {
 344         ASSERT (ring);
 345         ASSERT (cell);
 346         ASSERT (cell != *ring);
 347         ASSERT (cell->next == NULL);
 348         ASSERT (cell->prev == NULL);
 349
 350         /* Insert back into the mix of available memory */
 351         if (*ring) {
 352                 cell->next = (*ring)->next;
 353                 cell->prev = *ring;
 354                 cell->next->prev = cell;
 355                 cell->prev->next = cell;
 356         } else {
 357                 cell->next = cell;
 358                 cell->prev = cell;
 359         }
 360
 361         *ring = cell;
 362         ASSERT (cell->next->prev == cell);
 363         ASSERT (cell->prev->next == cell);
 364 }
 365
 366 static void
 367 sec_remove_cell_ring (Cell **ring, Cell *cell)
 368 {
 369         ASSERT (ring);
 370         ASSERT (*ring);
 371         ASSERT (cell->next);
 372         ASSERT (cell->prev);
 373
 374         ASSERT (cell->next->prev == cell);
 375         ASSERT (cell->prev->next == cell);
 376
 377         if (cell == *ring) {
 378                 /* The last meta? */
 379                 if (cell->next == cell) {
 380                         ASSERT (cell->prev == cell);
 381                         *ring = NULL;
 382
 383                 /* Just pointing to this meta */
 384                 } else {
 385                         ASSERT (cell->prev != cell);
 386                         *ring = cell->next;
 387                 }
 388         }
 389
 390         cell->next->prev = cell->prev;
 391         cell->prev->next = cell->next;
 392         cell->next = cell->prev = NULL;
 393
 394         ASSERT (*ring != cell);
 395 }
 396
 397 static inline void*
 398 sec_cell_to_memory (Cell *cell)
 399 {
 400         return cell->words + 1;
 401 }
 402
 403 static inline int
 404 sec_is_valid_word (Block *block, word_t *word)
 405 {
 406         return (word >= block->words && word < block->words + block->n_words);
 407 }
 408
 409 static inline void
 410 sec_clear_undefined (void *memory,
 411                      size_t from,
 412                      size_t to)
 413 {
 414         char *ptr = memory;
 415         ASSERT (from <= to);
 416 #ifdef WITH_VALGRIND
 417         VALGRIND_MAKE_MEM_UNDEFINED (ptr + from, to - from);
 418 #endif
 419         memset (ptr + from, 0, to - from);
 420 #ifdef WITH_VALGRIND
 421         VALGRIND_MAKE_MEM_UNDEFINED (ptr + from, to - from);
 422 #endif
 423 }
 424 static inline void
 425 sec_clear_noaccess (void *memory, size_t from, size_t to)
 426 {
 427         char *ptr = memory;
 428         ASSERT (from <= to);
 429 #ifdef WITH_VALGRIND
 430         VALGRIND_MAKE_MEM_UNDEFINED (ptr + from, to - from);
 431 #endif
 432         memset (ptr + from, 0, to - from);
 433 #ifdef WITH_VALGRIND
 434         VALGRIND_MAKE_MEM_NOACCESS (ptr + from, to - from);
 435 #endif
 436 }
 437
 438 static Cell*
 439 sec_neighbor_before (Block *block, Cell *cell)
 440 {
 441         word_t *word;
 442
 443         ASSERT (cell);
 444         ASSERT (block);
 445
 446         word = cell->words - 1;
 447         if (!sec_is_valid_word (block, word))
 448                 return NULL;
 449
 450 #ifdef WITH_VALGRIND
 451         VALGRIND_MAKE_MEM_DEFINED (word, sizeof (word_t));
 452 #endif
 453
 454         cell = *word;
 455         sec_check_guards (cell);
 456
 457 #ifdef WITH_VALGRIND
 458         VALGRIND_MAKE_MEM_NOACCESS (word, sizeof (word_t));
 459 #endif
 460
 461         return cell;
 462 }
 463
 464 static Cell*
 465 sec_neighbor_after (Block *block, Cell *cell)
 466 {
 467         word_t *word;
 468
 469         ASSERT (cell);
 470         ASSERT (block);
 471
 472         word = cell->words + cell->n_words;
 473         if (!sec_is_valid_word (block, word))
 474                 return NULL;
 475
 476 #ifdef WITH_VALGRIND
 477         VALGRIND_MAKE_MEM_DEFINED (word, sizeof (word_t));
 478 #endif
 479
 480         cell = *word;
 481         sec_check_guards (cell);
 482
 483 #ifdef WITH_VALGRIND
 484         VALGRIND_MAKE_MEM_NOACCESS (word, sizeof (word_t));
 485 #endif
 486
 487         return cell;
 488 }
 489
 490 static void*
 491 sec_alloc (Block *block,
 492            const char *tag,
 493            size_t length)
 494 {
 495         Cell *cell, *other;
 496         size_t n_words;
 497         void *memory;
 498
 499         ASSERT (block);
 500         ASSERT (length);
 501         ASSERT (tag);
 502
 503         if (!block->unused_cells)
 504                 return NULL;
 505
 506         /*
 507          * Each memory allocation is aligned to a pointer size, and
 508          * then, sandwidched between two pointers to its meta data.
 509          * These pointers also act as guards.
 510          *
 511          * We allocate memory in units of sizeof (void*)
 512          */
 513
 514         n_words = sec_size_to_words (length) + 2;
 515
 516         /* Look for a cell of at least our required size */
 517         cell = block->unused_cells;
 518         while (cell->n_words < n_words) {
 519                 cell = cell->next;
 520                 if (cell == block->unused_cells) {
 521                         cell = NULL;
 522                         break;
 523                 }
 524         }
 525
 526         if (!cell)
 527                 return NULL;
 528
 529         ASSERT (cell->tag == NULL);
 530         ASSERT (cell->requested == 0);
 531         ASSERT (cell->prev);
 532         ASSERT (cell->words);
 533         sec_check_guards (cell);
 534
 535         /* Steal from the cell if it's too long */
 536         if (cell->n_words > n_words + WASTE) {
 537                 other = pool_alloc ();
 538                 if (!other)
 539                         return NULL;
 540                 other->n_words = n_words;
 541                 other->words = cell->words;
 542                 cell->n_words -= n_words;
 543                 cell->words += n_words;
 544
 545                 sec_write_guards (other);
 546                 sec_write_guards (cell);
 547
 548                 cell = other;
 549         }
 550
 551         if (cell->next)
 552                 sec_remove_cell_ring (&block->unused_cells, cell);
 553
 554         ++block->n_used;
 555         cell->tag = tag;
 556         cell->requested = length;
 557         sec_insert_cell_ring (&block->used_cells, cell);
 558         memory = sec_cell_to_memory (cell);
 559
 560 #ifdef WITH_VALGRIND
 561         VALGRIND_MAKE_MEM_UNDEFINED (memory, length);
 562 #endif
 563
 564         return memset (memory, 0, length);
 565 }
 566
 567 static void*
 568 sec_free (Block *block, void *memory)
 569 {
 570         Cell *cell, *other;
 571         word_t *word;
 572
 573         ASSERT (block);
 574         ASSERT (memory);
 575
 576         word = memory;
 577         --word;
 578
 579 #ifdef WITH_VALGRIND
 580         VALGRIND_MAKE_MEM_DEFINED (word, sizeof (word_t));
 581 #endif
 582
 583         /* Lookup the meta for this memory block (using guard pointer) */
 584         ASSERT (sec_is_valid_word (block, word));
 585         ASSERT (pool_valid (*word));
 586         cell = *word;
 587
 588 #ifdef WITH_VALGRIND
 589         VALGRIND_MAKE_MEM_DEFINED (cell->words, cell->n_words * sizeof (word_t));
 590 #endif
 591
 592         sec_check_guards (cell);
 593         sec_clear_noaccess (memory, 0, cell->requested);
 594
 595         sec_check_guards (cell);
 596         ASSERT (cell->requested > 0);
 597         ASSERT (cell->tag != NULL);
 598
 599         /* Remove from the used cell ring */
 600         sec_remove_cell_ring (&block->used_cells, cell);
 601
 602         /* Find previous unallocated neighbor, and merge if possible */
 603         other = sec_neighbor_before (block, cell);
 604         if (other && other->requested == 0) {
 605                 ASSERT (other->tag == NULL);
 606                 ASSERT (other->next && other->prev);
 607                 other->n_words += cell->n_words;
 608                 sec_write_guards (other);
 609                 pool_free (cell);
 610                 cell = other;
 611         }
 612
 613         /* Find next unallocated neighbor, and merge if possible */
 614         other = sec_neighbor_after (block, cell);
 615         if (other && other->requested == 0) {
 616                 ASSERT (other->tag == NULL);
 617                 ASSERT (other->next && other->prev);
 618                 other->n_words += cell->n_words;
 619                 other->words = cell->words;
 620                 if (cell->next)
 621                         sec_remove_cell_ring (&block->unused_cells, cell);
 622                 sec_write_guards (other);
 623                 pool_free (cell);
 624                 cell = other;
 625         }
 626
 627         /* Add to the unused list if not already there */
 628         if (!cell->next)
 629                 sec_insert_cell_ring (&block->unused_cells, cell);
 630
 631         cell->tag = NULL;
 632         cell->requested = 0;
 633         --block->n_used;
 634         return NULL;
 635 }
 636
 637 static void
 638 memcpy_with_vbits (void *dest,
 639                    void *src,
 640                    size_t length)
 641 {
 642 #ifdef WITH_VALGRIND
 643         int vbits_setup = 0;
 644         void *vbits = NULL;
 645
 646         if (RUNNING_ON_VALGRIND) {
 647                 vbits = malloc (length);
 648                 if (vbits != NULL)
 649                         vbits_setup = VALGRIND_GET_VBITS (src, vbits, length);
 650                 VALGRIND_MAKE_MEM_DEFINED (src, length);
 651         }
 652 #endif
 653
 654         memcpy (dest, src, length);
 655
 656 #ifdef WITH_VALGRIND
 657         if (vbits_setup == 1) {
 658                 VALGRIND_SET_VBITS (dest, vbits, length);
 659                 VALGRIND_SET_VBITS (src, vbits, length);
 660         }
 661         free (vbits);
 662 #endif
 663 }
 664
 665 static void*
 666 sec_realloc (Block *block,
 667              const char *tag,
 668              void *memory,
 669              size_t length)
 670 {
 671         Cell *cell, *other;
 672         word_t *word;
 673         size_t n_words;
 674         size_t valid;
 675         void *alloc;
 676
 677         /* Standard realloc behavior, should have been handled elsewhere */
 678         ASSERT (memory != NULL);
 679         ASSERT (length > 0);
 680         ASSERT (tag != NULL);
 681
 682         /* Dig out where the meta should be */
 683         word = memory;
 684         --word;
 685
 686 #ifdef WITH_VALGRIND
 687         VALGRIND_MAKE_MEM_DEFINED (word, sizeof (word_t));
 688 #endif
 689
 690         ASSERT (sec_is_valid_word (block, word));
 691         ASSERT (pool_valid (*word));
 692         cell = *word;
 693
 694         /* Validate that it's actually for real */
 695         sec_check_guards (cell);
 696         ASSERT (cell->requested > 0);
 697         ASSERT (cell->tag != NULL);
 698
 699         /* The amount of valid data */
 700         valid = cell->requested;
 701
 702         /* How many words we actually want */
 703         n_words = sec_size_to_words (length) + 2;
 704
 705         /* Less memory is required than is in the cell */
 706         if (n_words <= cell->n_words) {
 707
 708                 /* TODO: No shrinking behavior yet */
 709                 cell->requested = length;
 710                 alloc = sec_cell_to_memory (cell);
 711
 712                 /*
 713                  * Even though we may be reusing the same cell, that doesn't
 714                  * mean that the allocation is shrinking. It could have shrunk
 715                  * and is now expanding back some.
 716                  */
 717                 if (length < valid)
 718                         sec_clear_undefined (alloc, length, valid);
 719
 720                 return alloc;
 721         }
 722
 723         /* Need braaaaaiiiiiinsss... */
 724         while (cell->n_words < n_words) {
 725
 726                 /* See if we have a neighbor who can give us some memory */
 727                 other = sec_neighbor_after (block, cell);
 728                 if (!other || other->requested != 0)
 729                         break;
 730
 731                 /* Eat the whole neighbor if not too big */
 732                 if (n_words - cell->n_words + WASTE >= other->n_words) {
 733                         cell->n_words += other->n_words;
 734                         sec_write_guards (cell);
 735                         sec_remove_cell_ring (&block->unused_cells, other);
 736                         pool_free (other);
 737
 738                 /* Steal from the neighbor */
 739                 } else {
 740                         other->words += n_words - cell->n_words;
 741                         other->n_words -= n_words - cell->n_words;
 742                         sec_write_guards (other);
 743                         cell->n_words = n_words;
 744                         sec_write_guards (cell);
 745                 }
 746         }
 747
 748         if (cell->n_words >= n_words) {
 749                 cell->requested = length;
 750                 cell->tag = tag;
 751                 alloc = sec_cell_to_memory (cell);
 752                 sec_clear_undefined (alloc, valid, length);
 753                 return alloc;
 754         }
 755
 756         /* That didn't work, try alloc/free */
 757         alloc = sec_alloc (block, tag, length);
 758         if (alloc) {
 759                 memcpy_with_vbits (alloc, memory, valid);
 760                 sec_free (block, memory);
 761         }
 762
 763         return alloc;
 764 }
 765
 766
 767 static size_t
 768 sec_allocated (Block *block, void *memory)
 769 {
 770         Cell *cell;
 771         word_t *word;
 772
 773         ASSERT (block);
 774         ASSERT (memory);
 775
 776         word = memory;
 777         --word;
 778
 779 #ifdef WITH_VALGRIND
 780         VALGRIND_MAKE_MEM_DEFINED (word, sizeof (word_t));
 781 #endif
 782
 783         /* Lookup the meta for this memory block (using guard pointer) */
 784         ASSERT (sec_is_valid_word (block, word));
 785         ASSERT (pool_valid (*word));
 786         cell = *word;
 787
 788         sec_check_guards (cell);
 789         ASSERT (cell->requested > 0);
 790         ASSERT (cell->tag != NULL);
 791
 792 #ifdef WITH_VALGRIND
 793         VALGRIND_MAKE_MEM_NOACCESS (word, sizeof (word_t));
 794 #endif
 795
 796         return cell->requested;
 797 }
 798
 799 static void
 800 sec_validate (Block *block)
 801 {
 802         Cell *cell;
 803         word_t *word, *last;
 804
 805 #ifdef WITH_VALGRIND
 806         if (RUNNING_ON_VALGRIND)
 807                 return;
 808 #endif
 809
 810         word = block->words;
 811         last = word + block->n_words;
 812
 813         for (;;) {
 814                 ASSERT (word < last);
 815
 816                 ASSERT (sec_is_valid_word (block, word));
 817                 ASSERT (pool_valid (*word));
 818                 cell = *word;
 819
 820                 /* Validate that it's actually for real */
 821                 sec_check_guards (cell);
 822
 823                 /* Is it an allocated block? */
 824                 if (cell->requested > 0) {
 825                         ASSERT (cell->tag != NULL);
 826                         ASSERT (cell->next != NULL);
 827                         ASSERT (cell->prev != NULL);
 828                         ASSERT (cell->next->prev == cell);
 829                         ASSERT (cell->prev->next == cell);
 830                         ASSERT (cell->requested <= (cell->n_words - 2) * sizeof (word_t));
 831
 832                 /* An unused block */
 833                 } else {
 834                         ASSERT (cell->tag == NULL);
 835                         ASSERT (cell->next != NULL);
 836                         ASSERT (cell->prev != NULL);
 837                         ASSERT (cell->next->prev == cell);
 838                         ASSERT (cell->prev->next == cell);
 839                 }
 840
 841                 word += cell->n_words;
 842                 if (word == last)
 843                         break;
 844         }
 845 }
 846
 847 /* -----------------------------------------------------------------------------
 848  * LOCKED MEMORY
 849  */
 850
 851 static void*
 852 sec_acquire_pages (size_t *sz,
 853                    const char *during_tag)
 854 {
 855         void *pages;
 856         unsigned long pgsize;
 857
 858         ASSERT (sz);
 859         ASSERT (*sz);
 860         ASSERT (during_tag);
 861
 862         /* Make sure sz is a multiple of the page size */
 863         pgsize = getpagesize ();
 864         *sz = (*sz + pgsize -1) & ~(pgsize - 1);
 865
 866 #if defined(HAVE_MLOCK)
 867         pages = mmap (0, *sz, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, -1, 0);
 868         if (pages == MAP_FAILED) {
 869                 if (show_warning && egg_secure_warnings)
 870                         fprintf (stderr, "couldn't map %lu bytes of memory (%s): %s\n",
 871                                  (unsigned long)*sz, during_tag, strerror (errno));
 872                 show_warning = 0;
 873                 return NULL;
 874         }
 875
 876         if (mlock (pages, *sz) < 0) {
 877                 if (show_warning && egg_secure_warnings && errno != EPERM) {
 878                         fprintf (stderr, "couldn't lock %lu bytes of memory (%s): %s\n",
 879                                  (unsigned long)*sz, during_tag, strerror (errno));
 880                         show_warning = 0;
 881                 }
 882                 munmap (pages, *sz);
 883                 return NULL;
 884         }
 885
 886         DEBUG_ALLOC ("gkr-secure-memory: new block ", *sz);
 887
 888         show_warning = 1;
 889         return pages;
 890
 891 #else
 892         if (show_warning && egg_secure_warnings)
 893                 fprintf (stderr, "your system does not support private memory");
 894         show_warning = 0;
 895         return NULL;
 896 #endif
 897
 898 }
 899
 900 static void
 901 sec_release_pages (void *pages, size_t sz)
 902 {
 903         ASSERT (pages);
 904         ASSERT (sz % getpagesize () == 0);
 905
 906 #if defined(HAVE_MLOCK)
 907         if (munlock (pages, sz) < 0 && egg_secure_warnings)
 908                 fprintf (stderr, "couldn't unlock private memory: %s\n", strerror (errno));
 909
 910         if (munmap (pages, sz) < 0 && egg_secure_warnings)
 911                 fprintf (stderr, "couldn't unmap private anonymous memory: %s\n", strerror (errno));
 912
 913         DEBUG_ALLOC ("gkr-secure-memory: freed block ", sz);
 914
 915 #else
 916         ASSERT (FALSE);
 917 #endif
 918 }
 919
 920 /* -----------------------------------------------------------------------------
 921  * MANAGE DIFFERENT BLOCKS
 922  */
 923
 924 static Block *all_blocks = NULL;
 925
 926 static Block*
 927 sec_block_create (size_t size,
 928                   const char *during_tag)
 929 {
 930         Block *block;
 931         Cell *cell;
 932
 933         ASSERT (during_tag);
 934
 935         /* We can force all all memory to be malloced */
 936         if (getenv ("SECMEM_FORCE_FALLBACK"))
 937                 return NULL;
 938
 939         block = pool_alloc ();
 940         if (!block)
 941                 return NULL;
 942
 943         cell = pool_alloc ();
 944         if (!cell) {
 945                 pool_free (block);
 946                 return NULL;
 947         }
 948
 949         /* The size above is a minimum, we're free to go bigger */
 950         if (size < DEFAULT_BLOCK_SIZE)
 951                 size = DEFAULT_BLOCK_SIZE;
 952
 953         block->words = sec_acquire_pages (&size, during_tag);
 954         block->n_words = size / sizeof (word_t);
 955         if (!block->words) {
 956                 pool_free (block);
 957                 pool_free (cell);
 958                 return NULL;
 959         }
 960
 961 #ifdef WITH_VALGRIND
 962         VALGRIND_MAKE_MEM_DEFINED (block->words, size);
 963 #endif
 964
 965         /* The first cell to allocate from */
 966         cell->words = block->words;
 967         cell->n_words = block->n_words;
 968         cell->requested = 0;
 969         sec_write_guards (cell);
 970         sec_insert_cell_ring (&block->unused_cells, cell);
 971
 972         block->next = all_blocks;
 973         all_blocks = block;
 974
 975         return block;
 976 }
 977
 978 static void
 979 sec_block_destroy (Block *block)
 980 {
 981         Block *bl, **at;
 982         Cell *cell;
 983
 984         ASSERT (block);
 985         ASSERT (block->words);
 986         ASSERT (block->n_used == 0);
 987
 988         /* Remove from the list */
 989         for (at = &all_blocks, bl = *at; bl; at = &bl->next, bl = *at) {
 990                 if (bl == block) {
 991                         *at = block->next;
 992                         break;
 993                 }
 994         }
 995
 996         /* Must have been found */
 997         ASSERT (bl == block);
 998         ASSERT (block->used_cells == NULL);
 999
1000         /* Release all the meta data cells */
1001         while (block->unused_cells) {
1002                 cell = block->unused_cells;
1003                 sec_remove_cell_ring (&block->unused_cells, cell);
1004                 pool_free (cell);
1005         }
1006
1007         /* Release all pages of secure memory */
1008         sec_release_pages (block->words, block->n_words * sizeof (word_t));
1009
1010         pool_free (block);
1011 }
1012
1013 /* ------------------------------------------------------------------------
1014  * PUBLIC FUNCTIONALITY
1015  */
1016
1017 void*
1018 egg_secure_alloc_full (const char *tag,
1019                        size_t length,
1020                        int flags)
1021 {
1022         Block *block;
1023         void *memory = NULL;
1024
1025         if (tag == NULL)
1026                 tag = "?";
1027
1028         if (length > 0xFFFFFFFF / 2) {
1029                 if (egg_secure_warnings)
1030                         fprintf (stderr, "tried to allocate an insane amount of memory: %lu\n",
1031                                  (unsigned long)length);
1032                 return NULL;
1033         }
1034
1035         /* Can't allocate zero bytes */
1036         if (length == 0)
1037                 return NULL;
1038
1039         DO_LOCK ();
1040
1041                 for (block = all_blocks; block; block = block->next) {
1042                         memory = sec_alloc (block, tag, length);
1043                         if (memory)
1044                                 break;
1045                 }
1046
1047                 /* None of the current blocks have space, allocate new */
1048                 if (!memory) {
1049                         block = sec_block_create (length, tag);
1050                         if (block)
1051                                 memory = sec_alloc (block, tag, length);
1052                 }
1053
1054 #ifdef WITH_VALGRIND
1055                 if (memory != NULL)
1056                         VALGRIND_MALLOCLIKE_BLOCK (memory, length, sizeof (void*), 1);
1057 #endif
1058
1059         DO_UNLOCK ();
1060
1061         if (!memory && (flags & EGG_SECURE_USE_FALLBACK) && EGG_SECURE_GLOBALS.fallback != NULL) {
1062                 memory = EGG_SECURE_GLOBALS.fallback (NULL, length);
1063                 if (memory) /* Our returned memory is always zeroed */
1064                         memset (memory, 0, length);
1065         }
1066
1067         if (!memory)
1068                 errno = ENOMEM;
1069
1070         return memory;
1071 }
1072
1073 void*
1074 egg_secure_realloc_full (const char *tag,
1075                          void *memory,
1076                          size_t length,
1077                          int flags)
1078 {
1079         Block *block = NULL;
1080         size_t previous = 0;
1081         int donew = 0;
1082         void *alloc = NULL;
1083
1084         if (tag == NULL)
1085                 tag = "?";
1086
1087         if (length > 0xFFFFFFFF / 2) {
1088                 if (egg_secure_warnings)
1089                         fprintf (stderr, "tried to allocate an insane amount of memory: %lu\n",
1090                                  (unsigned long)length);
1091                 return NULL;
1092         }
1093
1094         if (memory == NULL)
1095                 return egg_secure_alloc_full (tag, length, flags);
1096         if (!length) {
1097                 egg_secure_free_full (memory, flags);
1098                 return NULL;
1099         }
1100
1101         DO_LOCK ();
1102
1103                 /* Find out where it belongs to */
1104                 for (block = all_blocks; block; block = block->next) {
1105                         if (sec_is_valid_word (block, memory)) {
1106                                 previous = sec_allocated (block, memory);
1107
1108 #ifdef WITH_VALGRIND
1109                                 /* Let valgrind think we are unallocating so that it'll validate */
1110                                 VALGRIND_FREELIKE_BLOCK (memory, sizeof (word_t));
1111 #endif
1112
1113                                 alloc = sec_realloc (block, tag, memory, length);
1114
1115 #ifdef WITH_VALGRIND
1116                                 /* Now tell valgrind about either the new block or old one */
1117                                 VALGRIND_MALLOCLIKE_BLOCK (alloc ? alloc : memory,
1118                                                            alloc ? length : previous,
1119                                                            sizeof (word_t), 1);
1120 #endif
1121                                 break;
1122                         }
1123                 }
1124
1125                 /* If it didn't work we may need to allocate a new block */
1126                 if (block && !alloc)
1127                         donew = 1;
1128
1129                 if (block && block->n_used == 0)
1130                         sec_block_destroy (block);
1131
1132         DO_UNLOCK ();
1133
1134         if (!block) {
1135                 if ((flags & EGG_SECURE_USE_FALLBACK) && EGG_SECURE_GLOBALS.fallback) {
1136                         /*
1137                          * In this case we can't zero the returned memory,
1138                          * because we don't know what the block size was.
1139                          */
1140                         return EGG_SECURE_GLOBALS.fallback (memory, length);
1141                 } else {
1142                         if (egg_secure_warnings)
1143                                 fprintf (stderr, "memory does not belong to secure memory pool: 0x%08lx\n",
1144                                          (unsigned long)memory);
1145                         ASSERT (0 && "memory does does not belong to secure memory pool");
1146                         return NULL;
1147                 }
1148         }
1149
1150         if (donew) {
1151                 alloc = egg_secure_alloc_full (tag, length, flags);
1152                 if (alloc) {
1153                         memcpy_with_vbits (alloc, memory, previous);
1154                         egg_secure_free_full (memory, flags);
1155                 }
1156         }
1157
1158         if (!alloc)
1159                 errno = ENOMEM;
1160
1161         return alloc;
1162 }
1163
1164 void
1165 egg_secure_free (void *memory)
1166 {
1167         egg_secure_free_full (memory, EGG_SECURE_USE_FALLBACK);
1168 }
1169
1170 void
1171 egg_secure_free_full (void *memory, int flags)
1172 {
1173         Block *block = NULL;
1174
1175         if (memory == NULL)
1176                 return;
1177
1178         DO_LOCK ();
1179
1180                 /* Find out where it belongs to */
1181                 for (block = all_blocks; block; block = block->next) {
1182                         if (sec_is_valid_word (block, memory))
1183                                 break;
1184                 }
1185
1186 #ifdef WITH_VALGRIND
1187                 /* We like valgrind's warnings, so give it a first whack at checking for errors */
1188                 if (block != NULL || !(flags & EGG_SECURE_USE_FALLBACK))
1189                         VALGRIND_FREELIKE_BLOCK (memory, sizeof (word_t));
1190 #endif
1191
1192                 if (block != NULL) {
1193                         sec_free (block, memory);
1194                         if (block->n_used == 0)
1195                                 sec_block_destroy (block);
1196                 }
1197
1198         DO_UNLOCK ();
1199
1200         if (!block) {
1201                 if ((flags & EGG_SECURE_USE_FALLBACK) && EGG_SECURE_GLOBALS.fallback) {
1202                         EGG_SECURE_GLOBALS.fallback (memory, 0);
1203                 } else {
1204                         if (egg_secure_warnings)
1205                                 fprintf (stderr, "memory does not belong to secure memory pool: 0x%08lx\n",
1206                                          (unsigned long)memory);
1207                         ASSERT (0 && "memory does does not belong to secure memory pool");
1208                 }
1209         }
1210 }
1211
1212 int
1213 egg_secure_check (const void *memory)
1214 {
1215         Block *block = NULL;
1216
1217         DO_LOCK ();
1218
1219                 /* Find out where it belongs to */
1220                 for (block = all_blocks; block; block = block->next) {
1221                         if (sec_is_valid_word (block, (word_t*)memory))
1222                                 break;
1223                 }
1224
1225         DO_UNLOCK ();
1226
1227         return block == NULL ? 0 : 1;
1228 }
1229
1230 void
1231 egg_secure_validate (void)
1232 {
1233         Block *block = NULL;
1234
1235         DO_LOCK ();
1236
1237                 for (block = all_blocks; block; block = block->next)
1238                         sec_validate (block);
1239
1240         DO_UNLOCK ();
1241 }
1242
1243
1244 static egg_secure_rec *
1245 records_for_ring (Cell *cell_ring,
1246                   egg_secure_rec *records,
1247                   unsigned int *count,
1248                   unsigned int *total)
1249 {
1250         egg_secure_rec *new_rec;
1251         unsigned int allocated = *count;
1252         Cell *cell;
1253
1254         cell = cell_ring;
1255         do {
1256                 if (*count >= allocated) {
1257                         new_rec = realloc (records, sizeof (egg_secure_rec) * (allocated + 32));
1258                         if (new_rec == NULL) {
1259                                 *count = 0;
1260                                 free (records);
1261                                 return NULL;
1262                         } else {
1263                                 records = new_rec;
1264                                 allocated += 32;
1265                         }
1266                 }
1267
1268                 if (cell != NULL) {
1269                         records[*count].request_length = cell->requested;
1270                         records[*count].block_length = cell->n_words * sizeof (word_t);
1271                         records[*count].tag = cell->tag;
1272                         (*count)++;
1273                         (*total) += cell->n_words;
1274                         cell = cell->next;
1275                 }
1276         } while (cell != NULL && cell != cell_ring);
1277
1278         return records;
1279 }
1280
1281 egg_secure_rec *
1282 egg_secure_records (unsigned int *count)
1283 {
1284         egg_secure_rec *records = NULL;
1285         Block *block = NULL;
1286         unsigned int total;
1287
1288         *count = 0;
1289
1290         DO_LOCK ();
1291
1292                 for (block = all_blocks; block != NULL; block = block->next) {
1293                         total = 0;
1294
1295                         records = records_for_ring (block->unused_cells, records, count, &total);
1296                         if (records == NULL)
1297                                 break;
1298                         records = records_for_ring (block->used_cells, records, count, &total);
1299                         if (records == NULL)
1300                                 break;
1301
1302                         /* Make sure this actualy accounts for all memory */
1303                         ASSERT (total == block->n_words);
1304                 }
1305
1306         DO_UNLOCK ();
1307
1308         return records;
1309 }
1310
1311 char*
1312 egg_secure_strdup_full (const char *tag,
1313                         const char *str,
1314                         int options)
1315 {
1316         size_t len;
1317         char *res;
1318
1319         if (!str)
1320                 return NULL;
1321
1322         len = strlen (str) + 1;
1323         res = (char *)egg_secure_alloc_full (tag, len, options);
1324         strcpy (res, str);
1325         return res;
1326 }
1327
1328 char *
1329 egg_secure_strndup_full (const char *tag,
1330                          const char *str,
1331                          size_t length,
1332                          int options)
1333 {
1334         size_t len;
1335         char *res;
1336         const char *end;
1337
1338         if (!str)
1339                 return NULL;
1340
1341         end = memchr (str, '\0', length);
1342         if (end != NULL)
1343                 length = (end - str);
1344         len = length + 1;
1345         res = (char *)egg_secure_alloc_full (tag, len, options);
1346         memcpy (res, str, len);
1347         return res;
1348 }
1349
1350 void
1351 egg_secure_clear (void *p, size_t length)
1352 {
1353         volatile char *vp;
1354
1355         if (p == NULL)
1356                 return;
1357
1358         vp = (volatile char*)p;
1359         while (length) {
1360                 *vp = 0xAA;
1361                 vp++;
1362                 length--;
1363         }
1364 }
1365
1366 void
1367 egg_secure_strclear (char *str)
1368 {
1369         if (!str)
1370                 return;
1371         egg_secure_clear ((unsigned char*)str, strlen (str));
1372 }
1373
1374 void
1375 egg_secure_strfree (char *str)
1376 {
1377         /*
1378          * If we're using unpageable 'secure' memory, then the free call
1379          * should zero out the memory, but because on certain platforms
1380          * we may be using normal memory, zero it out here just in case.
1381          */
1382
1383         egg_secure_strclear (str);
1384         egg_secure_free_full (str, EGG_SECURE_USE_FALLBACK);
1385 }