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