Annotation of src/usr.bin/ssh/monitor_mm.c, Revision 1.1
1.1 ! provos 1: /*
! 2: * Copyright 2002 Niels Provos <provos@citi.umich.edu>
! 3: * All rights reserved.
! 4: *
! 5: * Redistribution and use in source and binary forms, with or without
! 6: * modification, are permitted provided that the following conditions
! 7: * are met:
! 8: * 1. Redistributions of source code must retain the above copyright
! 9: * notice, this list of conditions and the following disclaimer.
! 10: * 2. Redistributions in binary form must reproduce the above copyright
! 11: * notice, this list of conditions and the following disclaimer in the
! 12: * documentation and/or other materials provided with the distribution.
! 13: *
! 14: * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
! 15: * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
! 16: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
! 17: * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
! 18: * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
! 19: * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
! 20: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
! 21: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
! 22: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
! 23: * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
! 24: */
! 25:
! 26: #include "includes.h"
! 27: RCSID("$OpenBSD$");
! 28:
! 29: #include <sys/mman.h>
! 30:
! 31: #include "ssh.h"
! 32: #include "xmalloc.h"
! 33: #include "log.h"
! 34: #include "monitor_mm.h"
! 35:
! 36: static int
! 37: mm_compare(struct mm_share *a, struct mm_share *b)
! 38: {
! 39: return ((char *)a->address - (char *)b->address);
! 40: }
! 41:
! 42: RB_GENERATE(mmtree, mm_share, next, mm_compare)
! 43:
! 44: static struct mm_share *
! 45: mm_make_entry(struct mm_master *mm, struct mmtree *head,
! 46: void *address, size_t size)
! 47: {
! 48: struct mm_share *tmp, *tmp2;
! 49:
! 50: if (mm->mmalloc == NULL)
! 51: tmp = xmalloc(sizeof(struct mm_share));
! 52: else
! 53: tmp = mm_xmalloc(mm->mmalloc, sizeof(struct mm_share));
! 54: tmp->address = address;
! 55: tmp->size = size;
! 56:
! 57: tmp2 = RB_INSERT(mmtree, head, tmp);
! 58: if (tmp2 != NULL)
! 59: fatal("mm_make_entry(%p): double address %p->%p(%d)",
! 60: mm, tmp2, address, size);
! 61:
! 62: return (tmp);
! 63: }
! 64:
! 65: /* Creates a shared memory area of a certain size */
! 66:
! 67: struct mm_master *
! 68: mm_create(struct mm_master *mmalloc, size_t size)
! 69: {
! 70: void *address;
! 71: struct mm_master *mm;
! 72:
! 73: if (mmalloc == NULL)
! 74: mm = xmalloc(sizeof(struct mm_master));
! 75: else
! 76: mm = mm_xmalloc(mmalloc, sizeof(struct mm_master));
! 77:
! 78: /*
! 79: * If the memory map has a mm_master it can be completely
! 80: * shared including authentication between the child
! 81: * and the client.
! 82: */
! 83: mm->mmalloc = mmalloc;
! 84:
! 85: address = mmap(NULL, size, PROT_WRITE|PROT_READ, MAP_ANON|MAP_SHARED,
! 86: -1, 0);
! 87: if (address == MAP_FAILED)
! 88: fatal("mmap(%d)", size);
! 89:
! 90: mm->address = address;
! 91: mm->size = size;
! 92:
! 93: RB_INIT(&mm->rb_free);
! 94: RB_INIT(&mm->rb_allocated);
! 95:
! 96: mm_make_entry(mm, &mm->rb_free, address, size);
! 97:
! 98: return (mm);
! 99: }
! 100:
! 101: /* Frees either the allocated or the free list */
! 102:
! 103: void
! 104: mm_freelist(struct mm_master *mmalloc, struct mmtree *head)
! 105: {
! 106: struct mm_share *mms, *next;
! 107:
! 108: for (mms = RB_ROOT(head); mms; mms = next) {
! 109: next = RB_NEXT(mmtree, head, mms);
! 110: RB_REMOVE(mmtree, head, mms);
! 111: if (mmalloc == NULL)
! 112: xfree(mms);
! 113: else
! 114: mm_free(mmalloc, mms);
! 115: }
! 116: }
! 117:
! 118: /* Destroys a memory mapped area */
! 119:
! 120: void
! 121: mm_destroy(struct mm_master *mm)
! 122: {
! 123: mm_freelist(mm->mmalloc, &mm->rb_free);
! 124: mm_freelist(mm->mmalloc, &mm->rb_allocated);
! 125:
! 126: if (munmap(mm->address, mm->size) == -1)
! 127: fatal("munmap(%p, %d)", mm->address, mm->size);
! 128: if (mm->mmalloc == NULL)
! 129: xfree(mm);
! 130: else
! 131: mm_free(mm->mmalloc, mm);
! 132: }
! 133:
! 134: void *
! 135: mm_xmalloc(struct mm_master *mm, size_t size)
! 136: {
! 137: void *address;
! 138:
! 139: address = mm_malloc(mm, size);
! 140: if (address == NULL)
! 141: fatal("%s: mm_malloc(%d)", __FUNCTION__, size);
! 142: return (address);
! 143: }
! 144:
! 145:
! 146: /* Allocates data from a memory mapped area */
! 147:
! 148: void *
! 149: mm_malloc(struct mm_master *mm, size_t size)
! 150: {
! 151: struct mm_share *mms, *tmp;
! 152:
! 153: if (size == 0)
! 154: fatal("mm_malloc: try to allocate 0 space");
! 155:
! 156: size = ((size + MM_MINSIZE - 1) / MM_MINSIZE) * MM_MINSIZE;
! 157:
! 158: RB_FOREACH(mms, mmtree, &mm->rb_free) {
! 159: if (mms->size >= size)
! 160: break;
! 161: }
! 162:
! 163: if (mms == NULL)
! 164: return (NULL);
! 165:
! 166: /* Debug */
! 167: memset(mms->address, 0xd0, size);
! 168:
! 169: tmp = mm_make_entry(mm, &mm->rb_allocated, mms->address, size);
! 170:
! 171: /* Does not change order in RB tree */
! 172: mms->size -= size;
! 173: mms->address = (u_char *)mms->address + size;
! 174:
! 175: if (mms->size == 0) {
! 176: RB_REMOVE(mmtree, &mm->rb_free, mms);
! 177: if (mm->mmalloc == NULL)
! 178: xfree(mms);
! 179: else
! 180: mm_free(mm->mmalloc, mms);
! 181: }
! 182:
! 183: return (tmp->address);
! 184: }
! 185:
! 186: /* Frees memory in a memory mapped area */
! 187:
! 188: void
! 189: mm_free(struct mm_master *mm, void *address)
! 190: {
! 191: struct mm_share *mms, *prev, tmp;
! 192:
! 193: tmp.address = address;
! 194: mms = RB_FIND(mmtree, &mm->rb_allocated, &tmp);
! 195: if (mms == NULL)
! 196: fatal("mm_free(%p): can not find %p", mm, address);
! 197:
! 198: /* Debug */
! 199: memset(mms->address, 0xd0, mms->size);
! 200:
! 201: /* Remove from allocated list and insert in free list */
! 202: RB_REMOVE(mmtree, &mm->rb_allocated, mms);
! 203: if (RB_INSERT(mmtree, &mm->rb_free, mms) != NULL)
! 204: fatal("mm_free(%p): double address %p", mm, address);
! 205:
! 206: /* Find previous entry */
! 207: prev = mms;
! 208: if (RB_LEFT(prev, next)) {
! 209: prev = RB_LEFT(prev, next);
! 210: while (RB_RIGHT(prev, next))
! 211: prev = RB_RIGHT(prev, next);
! 212: } else {
! 213: if (RB_PARENT(prev, next) &&
! 214: (prev == RB_RIGHT(RB_PARENT(prev, next), next)))
! 215: prev = RB_PARENT(prev, next);
! 216: else {
! 217: while (RB_PARENT(prev, next) &&
! 218: (prev == RB_LEFT(RB_PARENT(prev, next), next)))
! 219: prev = RB_PARENT(prev, next);
! 220: prev = RB_PARENT(prev, next);
! 221: }
! 222: }
! 223:
! 224: /* Check if range does not overlap */
! 225: if (prev != NULL && MM_ADDRESS_END(prev) > address)
! 226: fatal("mm_free: memory corruption: %p(%d) > %p",
! 227: prev->address, prev->size, address);
! 228:
! 229: /* See if we can merge backwards */
! 230: if (prev != NULL && MM_ADDRESS_END(prev) == address) {
! 231: prev->size += mms->size;
! 232: RB_REMOVE(mmtree, &mm->rb_free, mms);
! 233: if (mm->mmalloc == NULL)
! 234: xfree(mms);
! 235: else
! 236: mm_free(mm->mmalloc, mms);
! 237: } else
! 238: prev = mms;
! 239:
! 240: if (prev == NULL)
! 241: return;
! 242:
! 243: /* Check if we can merge forwards */
! 244: mms = RB_NEXT(mmtree, &mm->rb_free, prev);
! 245: if (mms == NULL)
! 246: return;
! 247:
! 248: if (MM_ADDRESS_END(prev) > mms->address)
! 249: fatal("mm_free: memory corruption: %p < %p(%d)",
! 250: mms->address, prev->address, prev->size);
! 251: if (MM_ADDRESS_END(prev) != mms->address)
! 252: return;
! 253:
! 254: prev->size += mms->size;
! 255: RB_REMOVE(mmtree, &mm->rb_free, mms);
! 256:
! 257: if (mm->mmalloc == NULL)
! 258: xfree(mms);
! 259: else
! 260: mm_free(mm->mmalloc, mms);
! 261: }
! 262:
! 263: void
! 264: mm_sync_list(struct mmtree *oldtree, struct mmtree *newtree,
! 265: struct mm_master *mm, struct mm_master *mmold)
! 266: {
! 267: struct mm_master *mmalloc = mm->mmalloc;
! 268: struct mm_share *mms, *new;
! 269:
! 270: /* Sync free list */
! 271: RB_FOREACH(mms, mmtree, oldtree) {
! 272: /* Check the values */
! 273: mm_memvalid(mmold, mms, sizeof(struct mm_share));
! 274: mm_memvalid(mm, mms->address, mms->size);
! 275:
! 276: new = mm_xmalloc(mmalloc, sizeof(struct mm_share));
! 277: memcpy(new, mms, sizeof(struct mm_share));
! 278: RB_INSERT(mmtree, newtree, new);
! 279: }
! 280: }
! 281:
! 282: void
! 283: mm_share_sync(struct mm_master **pmm, struct mm_master **pmmalloc)
! 284: {
! 285: struct mm_master *mm;
! 286: struct mm_master *mmalloc;
! 287: struct mm_master *mmold;
! 288: struct mmtree rb_free, rb_allocated;
! 289:
! 290: debug3("%s: Share sync", __FUNCTION__);
! 291:
! 292: mm = *pmm;
! 293: mmold = mm->mmalloc;
! 294: mm_memvalid(mmold, mm, sizeof(*mm));
! 295:
! 296: mmalloc = mm_create(NULL, mm->size);
! 297: mm = mm_xmalloc(mmalloc, sizeof(struct mm_master));
! 298: memcpy(mm, *pmm, sizeof(struct mm_master));
! 299: mm->mmalloc = mmalloc;
! 300:
! 301: rb_free = mm->rb_free;
! 302: rb_allocated = mm->rb_allocated;
! 303:
! 304: RB_INIT(&mm->rb_free);
! 305: RB_INIT(&mm->rb_allocated);
! 306:
! 307: mm_sync_list(&rb_free, &mm->rb_free, mm, mmold);
! 308: mm_sync_list(&rb_allocated, &mm->rb_allocated, mm, mmold);
! 309:
! 310: mm_destroy(mmold);
! 311:
! 312: *pmm = mm;
! 313: *pmmalloc = mmalloc;
! 314:
! 315: debug3("%s: Share sync end", __FUNCTION__);
! 316: }
! 317:
! 318: void
! 319: mm_memvalid(struct mm_master *mm, void *address, size_t size)
! 320: {
! 321: void *end = (u_char *)address + size;
! 322:
! 323: if (address < mm->address)
! 324: fatal("mm_memvalid: address too small: %p", address);
! 325: if (end < address)
! 326: fatal("mm_memvalid: end < address: %p < %p", end, address);
! 327: if (end > (void *)((u_char *)mm->address + mm->size))
! 328: fatal("mm_memvalid: address too large: %p", address);
! 329: }