summaryrefslogtreecommitdiffstats
path: root/free.c
blob: c33485c4ec9e728d58a89414b2a3ce2a5b25614d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
/* ----------------------------------------------------------------------- *
 *   
 *   Copyright 2000-2008 H. Peter Anvin - All Rights Reserved
 *
 *   This program is free software; you can redistribute it and/or modify
 *   it under the terms of the GNU Lesser General Public License as
 *   published by the Free Software Foundation, Inc.,
 *   59 Temple Place Ste 330, Boston MA 02111-1307, USA, version 2.1,
 *   incorporated herein by reference.
 *
 * ----------------------------------------------------------------------- */

/*
 * free.c
 *
 * Provides free() for the persistent memory allocator.
 */

#include <assert.h>
#include <stdlib.h>
#include <inttypes.h>
#include <limits.h>
#include <string.h>

#include "lpsm.h"
#include "internals.h"
#include "bitops.h"

static void lpsm_free_chunk(int xbit, int rorder)
{
  if ( rorder > 0 ) {
    int bxbit = xbit^1;		/* Buddy xbit */
    if ( test_bit(AH->free_bitmap, bxbit) ) {
      /* Buddy is free. */
      clr_bit(AH->free_bitmap, bxbit);
      DPRINTF(("buddy: coalescing rorder %2d %d %d -> %2d %d\n",
	       rorder, xbit, bxbit, rorder-1, (xbit >> 1)));
      lpsm_free_chunk((xbit >> 1), rorder-1);
      return;
    }
  }
  set_bit(AH->free_bitmap, xbit);
}

/*
 * This routine finds the parameters for one particular
 * buddy allocation from its address; used by free() and
 * realloc().
 */
struct buddy_params lpsm_find_alloc_buddy(const void *ptr)
{
  struct buddy_params bp;
  uintptr_t offset = (uintptr_t)ptr - (uintptr_t)AH->data_start;
  int order, rorder;
  int xbit, obit;

  assert(offset < (1UL << AH->arena_size_lg2)); /* Not inside the arena?? */

  for ( rorder = 0, order = AH->arena_size_lg2 ;
	order >= BUDDY_ORDER_MIN ;
	rorder++, order-- ) {
    if ( offset & ((1UL << order)-1) )
      continue;			/* Can't be this order */

    obit = 1 << rorder;
    xbit = obit + (offset >> order);
    
    if ( test_bit(AH->alloc_bitmap, xbit) ) {
      /* We're this order... */
      bp.xbit = xbit;  bp.rorder = rorder;
      return bp;
    }
  }

  abort();			/* Freeing bogus memory? */
}
  
void lpsm_free_buddy(void *ptr)
{
  struct buddy_params bp;

  DPRINTF(("buddy: freeing allocation at %p\n", ptr));
  bp = lpsm_find_alloc_buddy(ptr);
  DPRINTF(("buddy: freeing rorder %2d %8d\n", bp.rorder, bp.xbit));
  clr_bit(AH->alloc_bitmap, bp.xbit);
  lpsm_free_chunk(bp.xbit, bp.rorder);
}

void lpsm_free_slab(void *ptr)
{
  struct slab_header *sh;
  struct slab_info   *si;
  int offset, which, free_count;
  unsigned char *slab_bitmap;

  /* Slab header should be at the start of the page */
  sh = (struct slab_header *)((uintptr_t)ptr & ~(BUDDY_SIZE_MIN-1));
  assert(sh->magic == SLAB_MAGIC);
  si = &AH->slab[sh->index];
  slab_bitmap = (unsigned char *)(sh+1);

  DPRINTF(("slab:  Freeing size %d slab at %p, %d/%d allocated\n",
	   si->size, ptr, si->count-sh->free_count, si->count));

  offset = ((uintptr_t)ptr & (BUDDY_SIZE_MIN-1)) - si->data_offset;
  assert(offset >= 0);
  which = offset/si->size;
  assert(offset == which*si->size);

  free_count = sh->free_count;
  si->alloc_slabs--;

  if ( free_count == si->count-1 ) {
    /* Deallocated the entire page; give back to buddy system */
    DPRINTF(("slab:  Returning page %p back to the buddy system\n", sh));
    *(sh->rev) = sh->next;	/* Remove from free list */
    if ( sh->next ) {
      sh->next->rev = sh->rev;
      assert(sh->next->index == sh->index);
    }
    si->total_pages--;
#ifndef NDEBUG
    /* This unfortunately makes the page dirty */
    memset(sh, 0, BUDDY_SIZE_MIN);
#endif
    lpsm_free_buddy(sh);
  } else {
    set_bit(slab_bitmap, which);
    sh->free_count = free_count+1;
    if ( free_count == 0 ) {
      /* Page is no longer full, add to free list */
      DPRINTF(("slab:  Adding page %p back onto free list for slab size %d\n",
	       sh, si->size));
      assert(sh->index == si - &AH->slab[0]);
      sh->rev  = &(si->list);
      sh->next = si->list;
      if ( sh->next ) {
	sh->next->rev = &(sh->next);
	assert(sh->next->index == sh->index);
      }
      si->list = sh;
    }
  }
}

void lpsm_free(void *ptr)
{
  /* Buddy allocations are ALWAYS page-aligned, SLAB allocations never */
  if ( ptr ) {
    if ( (uintptr_t)ptr & (BUDDY_SIZE_MIN-1) )
      lpsm_free_slab(ptr);
    else
      lpsm_free_buddy(ptr);
  }
}