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