monitor_mm.c revision 255767
1255767Sdes/* $OpenBSD: monitor_mm.c,v 1.17 2013/05/17 00:13:13 djm Exp $ */ 298675Sdes/* 398675Sdes * Copyright 2002 Niels Provos <provos@citi.umich.edu> 498675Sdes * All rights reserved. 598675Sdes * 698675Sdes * Redistribution and use in source and binary forms, with or without 798675Sdes * modification, are permitted provided that the following conditions 898675Sdes * are met: 998675Sdes * 1. Redistributions of source code must retain the above copyright 1098675Sdes * notice, this list of conditions and the following disclaimer. 1198675Sdes * 2. Redistributions in binary form must reproduce the above copyright 1298675Sdes * notice, this list of conditions and the following disclaimer in the 1398675Sdes * documentation and/or other materials provided with the distribution. 1498675Sdes * 1598675Sdes * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 1698675Sdes * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 1798675Sdes * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 1898675Sdes * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 1998675Sdes * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 2098675Sdes * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2198675Sdes * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2298675Sdes * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2398675Sdes * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 2498675Sdes * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2598675Sdes */ 2698675Sdes 2798675Sdes#include "includes.h" 2898675Sdes 29162852Sdes#include <sys/types.h> 3098937Sdes#ifdef HAVE_SYS_MMAN_H 3198675Sdes#include <sys/mman.h> 3298937Sdes#endif 33162852Sdes#include <sys/param.h> 34162852Sdes#include "openbsd-compat/sys-tree.h" 3598675Sdes 36162852Sdes#include <errno.h> 37162852Sdes#include <stdarg.h> 38255767Sdes#include <stdlib.h> 39162852Sdes#include <string.h> 40162852Sdes 41162852Sdes#include "xmalloc.h" 4298675Sdes#include "ssh.h" 4398675Sdes#include "log.h" 4498675Sdes#include "monitor_mm.h" 4598675Sdes 4698675Sdesstatic int 4798675Sdesmm_compare(struct mm_share *a, struct mm_share *b) 4898675Sdes{ 49106121Sdes long diff = (char *)a->address - (char *)b->address; 50106121Sdes 51106121Sdes if (diff == 0) 52106121Sdes return (0); 53106121Sdes else if (diff < 0) 54106121Sdes return (-1); 55106121Sdes else 56106121Sdes return (1); 5798675Sdes} 5898675Sdes 5998675SdesRB_GENERATE(mmtree, mm_share, next, mm_compare) 6098675Sdes 6198675Sdesstatic struct mm_share * 6298675Sdesmm_make_entry(struct mm_master *mm, struct mmtree *head, 6398675Sdes void *address, size_t size) 6498675Sdes{ 6598675Sdes struct mm_share *tmp, *tmp2; 6698675Sdes 6798675Sdes if (mm->mmalloc == NULL) 6898675Sdes tmp = xmalloc(sizeof(struct mm_share)); 6998675Sdes else 7098675Sdes tmp = mm_xmalloc(mm->mmalloc, sizeof(struct mm_share)); 7198675Sdes tmp->address = address; 7298675Sdes tmp->size = size; 7398675Sdes 7498675Sdes tmp2 = RB_INSERT(mmtree, head, tmp); 7598675Sdes if (tmp2 != NULL) 7698675Sdes fatal("mm_make_entry(%p): double address %p->%p(%lu)", 7798675Sdes mm, tmp2, address, (u_long)size); 7898675Sdes 7998675Sdes return (tmp); 8098675Sdes} 8198675Sdes 8298675Sdes/* Creates a shared memory area of a certain size */ 8398675Sdes 8498675Sdesstruct mm_master * 8598675Sdesmm_create(struct mm_master *mmalloc, size_t size) 8698675Sdes{ 8798675Sdes void *address; 8898675Sdes struct mm_master *mm; 8998675Sdes 9098675Sdes if (mmalloc == NULL) 9198675Sdes mm = xmalloc(sizeof(struct mm_master)); 9298675Sdes else 9398675Sdes mm = mm_xmalloc(mmalloc, sizeof(struct mm_master)); 9498675Sdes 9598675Sdes /* 9698675Sdes * If the memory map has a mm_master it can be completely 9798675Sdes * shared including authentication between the child 9898675Sdes * and the client. 9998675Sdes */ 10098675Sdes mm->mmalloc = mmalloc; 10198675Sdes 102106121Sdes address = xmmap(size); 103146998Sdes if (address == (void *)MAP_FAILED) 10498675Sdes fatal("mmap(%lu): %s", (u_long)size, strerror(errno)); 10598675Sdes 10698675Sdes mm->address = address; 10798675Sdes mm->size = size; 10898675Sdes 10998675Sdes RB_INIT(&mm->rb_free); 11098675Sdes RB_INIT(&mm->rb_allocated); 11198675Sdes 11298675Sdes mm_make_entry(mm, &mm->rb_free, address, size); 11398675Sdes 11498675Sdes return (mm); 11598675Sdes} 11698675Sdes 11798675Sdes/* Frees either the allocated or the free list */ 11898675Sdes 11998675Sdesstatic void 12098675Sdesmm_freelist(struct mm_master *mmalloc, struct mmtree *head) 12198675Sdes{ 12298675Sdes struct mm_share *mms, *next; 12398675Sdes 12498675Sdes for (mms = RB_ROOT(head); mms; mms = next) { 12598675Sdes next = RB_NEXT(mmtree, head, mms); 12698675Sdes RB_REMOVE(mmtree, head, mms); 12798675Sdes if (mmalloc == NULL) 128255767Sdes free(mms); 12998675Sdes else 13098675Sdes mm_free(mmalloc, mms); 13198675Sdes } 13298675Sdes} 13398675Sdes 13498675Sdes/* Destroys a memory mapped area */ 13598675Sdes 13698675Sdesvoid 13798675Sdesmm_destroy(struct mm_master *mm) 13898675Sdes{ 13998675Sdes mm_freelist(mm->mmalloc, &mm->rb_free); 14098675Sdes mm_freelist(mm->mmalloc, &mm->rb_allocated); 14198675Sdes 142106121Sdes#ifdef HAVE_MMAP 14398675Sdes if (munmap(mm->address, mm->size) == -1) 14498675Sdes fatal("munmap(%p, %lu): %s", mm->address, (u_long)mm->size, 14598675Sdes strerror(errno)); 14698937Sdes#else 14799060Sdes fatal("%s: UsePrivilegeSeparation=yes and Compression=yes not supported", 14898937Sdes __func__); 14998937Sdes#endif 15098675Sdes if (mm->mmalloc == NULL) 151255767Sdes free(mm); 15298675Sdes else 15398675Sdes mm_free(mm->mmalloc, mm); 15498675Sdes} 15598675Sdes 15698675Sdesvoid * 15798675Sdesmm_xmalloc(struct mm_master *mm, size_t size) 15898675Sdes{ 15998675Sdes void *address; 16098675Sdes 16198675Sdes address = mm_malloc(mm, size); 16298675Sdes if (address == NULL) 16398675Sdes fatal("%s: mm_malloc(%lu)", __func__, (u_long)size); 16498675Sdes return (address); 16598675Sdes} 16698675Sdes 16798675Sdes 16898675Sdes/* Allocates data from a memory mapped area */ 16998675Sdes 17098675Sdesvoid * 17198675Sdesmm_malloc(struct mm_master *mm, size_t size) 17298675Sdes{ 17398675Sdes struct mm_share *mms, *tmp; 17498675Sdes 17598675Sdes if (size == 0) 17698675Sdes fatal("mm_malloc: try to allocate 0 space"); 177106121Sdes if (size > SIZE_T_MAX - MM_MINSIZE + 1) 178106121Sdes fatal("mm_malloc: size too big"); 17998675Sdes 180106121Sdes size = ((size + (MM_MINSIZE - 1)) / MM_MINSIZE) * MM_MINSIZE; 18198675Sdes 18298675Sdes RB_FOREACH(mms, mmtree, &mm->rb_free) { 18398675Sdes if (mms->size >= size) 18498675Sdes break; 18598675Sdes } 18698675Sdes 18798675Sdes if (mms == NULL) 18898675Sdes return (NULL); 18998675Sdes 19098675Sdes /* Debug */ 19198675Sdes memset(mms->address, 0xd0, size); 19298675Sdes 19398675Sdes tmp = mm_make_entry(mm, &mm->rb_allocated, mms->address, size); 19498675Sdes 19598675Sdes /* Does not change order in RB tree */ 19698675Sdes mms->size -= size; 19798675Sdes mms->address = (u_char *)mms->address + size; 19898675Sdes 19998675Sdes if (mms->size == 0) { 20098675Sdes RB_REMOVE(mmtree, &mm->rb_free, mms); 20198675Sdes if (mm->mmalloc == NULL) 202255767Sdes free(mms); 20398675Sdes else 20498675Sdes mm_free(mm->mmalloc, mms); 20598675Sdes } 20698675Sdes 20798675Sdes return (tmp->address); 20898675Sdes} 20998675Sdes 21098675Sdes/* Frees memory in a memory mapped area */ 21198675Sdes 21298675Sdesvoid 21398675Sdesmm_free(struct mm_master *mm, void *address) 21498675Sdes{ 21598675Sdes struct mm_share *mms, *prev, tmp; 21698675Sdes 21798675Sdes tmp.address = address; 21898675Sdes mms = RB_FIND(mmtree, &mm->rb_allocated, &tmp); 21998675Sdes if (mms == NULL) 22098675Sdes fatal("mm_free(%p): can not find %p", mm, address); 22198675Sdes 22298675Sdes /* Debug */ 22398675Sdes memset(mms->address, 0xd0, mms->size); 22498675Sdes 22598675Sdes /* Remove from allocated list and insert in free list */ 22698675Sdes RB_REMOVE(mmtree, &mm->rb_allocated, mms); 22798675Sdes if (RB_INSERT(mmtree, &mm->rb_free, mms) != NULL) 22898675Sdes fatal("mm_free(%p): double address %p", mm, address); 22998675Sdes 23098675Sdes /* Find previous entry */ 23198675Sdes prev = mms; 23298675Sdes if (RB_LEFT(prev, next)) { 23398675Sdes prev = RB_LEFT(prev, next); 23498675Sdes while (RB_RIGHT(prev, next)) 23598675Sdes prev = RB_RIGHT(prev, next); 23698675Sdes } else { 23798675Sdes if (RB_PARENT(prev, next) && 23898675Sdes (prev == RB_RIGHT(RB_PARENT(prev, next), next))) 23998675Sdes prev = RB_PARENT(prev, next); 24098675Sdes else { 24198675Sdes while (RB_PARENT(prev, next) && 24298675Sdes (prev == RB_LEFT(RB_PARENT(prev, next), next))) 24398675Sdes prev = RB_PARENT(prev, next); 24498675Sdes prev = RB_PARENT(prev, next); 24598675Sdes } 24698675Sdes } 24798675Sdes 24898675Sdes /* Check if range does not overlap */ 24998675Sdes if (prev != NULL && MM_ADDRESS_END(prev) > address) 25098675Sdes fatal("mm_free: memory corruption: %p(%lu) > %p", 25198675Sdes prev->address, (u_long)prev->size, address); 25298675Sdes 25398675Sdes /* See if we can merge backwards */ 25498675Sdes if (prev != NULL && MM_ADDRESS_END(prev) == address) { 25598675Sdes prev->size += mms->size; 25698675Sdes RB_REMOVE(mmtree, &mm->rb_free, mms); 25798675Sdes if (mm->mmalloc == NULL) 258255767Sdes free(mms); 25998675Sdes else 26098675Sdes mm_free(mm->mmalloc, mms); 26198675Sdes } else 26298675Sdes prev = mms; 26398675Sdes 26498675Sdes if (prev == NULL) 26598675Sdes return; 26698675Sdes 26798675Sdes /* Check if we can merge forwards */ 26898675Sdes mms = RB_NEXT(mmtree, &mm->rb_free, prev); 26998675Sdes if (mms == NULL) 27098675Sdes return; 27198675Sdes 27298675Sdes if (MM_ADDRESS_END(prev) > mms->address) 27398675Sdes fatal("mm_free: memory corruption: %p < %p(%lu)", 27498675Sdes mms->address, prev->address, (u_long)prev->size); 27598675Sdes if (MM_ADDRESS_END(prev) != mms->address) 27698675Sdes return; 27798675Sdes 27898675Sdes prev->size += mms->size; 27998675Sdes RB_REMOVE(mmtree, &mm->rb_free, mms); 28098675Sdes 28198675Sdes if (mm->mmalloc == NULL) 282255767Sdes free(mms); 28398675Sdes else 28498675Sdes mm_free(mm->mmalloc, mms); 28598675Sdes} 28698675Sdes 28798675Sdesstatic void 28898675Sdesmm_sync_list(struct mmtree *oldtree, struct mmtree *newtree, 28998675Sdes struct mm_master *mm, struct mm_master *mmold) 29098675Sdes{ 29198675Sdes struct mm_master *mmalloc = mm->mmalloc; 29298675Sdes struct mm_share *mms, *new; 29398675Sdes 29498675Sdes /* Sync free list */ 29598675Sdes RB_FOREACH(mms, mmtree, oldtree) { 29698675Sdes /* Check the values */ 29798675Sdes mm_memvalid(mmold, mms, sizeof(struct mm_share)); 29898675Sdes mm_memvalid(mm, mms->address, mms->size); 29998675Sdes 30098675Sdes new = mm_xmalloc(mmalloc, sizeof(struct mm_share)); 30198675Sdes memcpy(new, mms, sizeof(struct mm_share)); 30298675Sdes RB_INSERT(mmtree, newtree, new); 30398675Sdes } 30498675Sdes} 30598675Sdes 30698675Sdesvoid 30798675Sdesmm_share_sync(struct mm_master **pmm, struct mm_master **pmmalloc) 30898675Sdes{ 30998675Sdes struct mm_master *mm; 31098675Sdes struct mm_master *mmalloc; 31198675Sdes struct mm_master *mmold; 31298675Sdes struct mmtree rb_free, rb_allocated; 31398675Sdes 31498675Sdes debug3("%s: Share sync", __func__); 31598675Sdes 31698675Sdes mm = *pmm; 31798675Sdes mmold = mm->mmalloc; 31898675Sdes mm_memvalid(mmold, mm, sizeof(*mm)); 31998675Sdes 32098675Sdes mmalloc = mm_create(NULL, mm->size); 32198675Sdes mm = mm_xmalloc(mmalloc, sizeof(struct mm_master)); 32298675Sdes memcpy(mm, *pmm, sizeof(struct mm_master)); 32398675Sdes mm->mmalloc = mmalloc; 32498675Sdes 32598675Sdes rb_free = mm->rb_free; 32698675Sdes rb_allocated = mm->rb_allocated; 32798675Sdes 32898675Sdes RB_INIT(&mm->rb_free); 32998675Sdes RB_INIT(&mm->rb_allocated); 33098675Sdes 33198675Sdes mm_sync_list(&rb_free, &mm->rb_free, mm, mmold); 33298675Sdes mm_sync_list(&rb_allocated, &mm->rb_allocated, mm, mmold); 33398675Sdes 33498675Sdes mm_destroy(mmold); 33598675Sdes 33698675Sdes *pmm = mm; 33798675Sdes *pmmalloc = mmalloc; 33898675Sdes 33998675Sdes debug3("%s: Share sync end", __func__); 34098675Sdes} 34198675Sdes 34298675Sdesvoid 34398675Sdesmm_memvalid(struct mm_master *mm, void *address, size_t size) 34498675Sdes{ 34598675Sdes void *end = (u_char *)address + size; 34698675Sdes 34798675Sdes if (address < mm->address) 34898675Sdes fatal("mm_memvalid: address too small: %p", address); 34998675Sdes if (end < address) 35098675Sdes fatal("mm_memvalid: end < address: %p < %p", end, address); 35198675Sdes if (end > (void *)((u_char *)mm->address + mm->size)) 35298675Sdes fatal("mm_memvalid: address too large: %p", address); 35398675Sdes} 354