monitor_mm.c

   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: monitor_mm.c,v 1.3 2002/03/19 10:41:32 markus Exp $");
  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 static 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 static 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 }