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