1/*
2 * Copyright (c) 2011 Apple Inc. All rights reserved.
3 *
4 * @APPLE_APACHE_LICENSE_HEADER_START@
5 *
6 * Licensed under the Apache License, Version 2.0 (the "License");
7 * you may not use this file except in compliance with the License.
8 * You may obtain a copy of the License at
9 *
10 *     http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 *
18 * @APPLE_APACHE_LICENSE_HEADER_END@
19 */
20/*
21    Region.cpp
22    Contiguous range of subzones.
23    Copyright (c) 2004-2011 Apple Inc. All rights reserved.
24 */
25
26#include "Configuration.h"
27#include "Definitions.h"
28#include "Environment.h"
29#include "Region.h"
30#include "Zone.h"
31
32namespace Auto {
33
34
35    //----- Region -----//
36
37
38    //
39    // new_region
40    //
41    // Construct and initialize a new region.
42    // First we get the memory that we will parcel out, then we build up the Region object itself
43    //
44    Region *Region::new_region(Zone *zone) {
45        usword_t allocation_size;                           // size of subzone region
46        void *allocation_address = NULL;                    // address of subzone region
47        unsigned nzones;
48
49#if UseArena
50        // take half the space for small/medium.  A better scheme might, in effect, preallocate the entire space,
51        // and then guard crossing into the large space in add_subzone.  The top of the large area would be before
52        // the bitmaps - stealing from the top subzones.
53        // For now, take half.  Chances are there won't be enough physical memory to exhaust this before swapping.
54        nzones = 1 << (arena_size_log2 - subzone_quantum_log2 - 1);
55        allocation_size = managed_size(nzones);
56        allocation_address = zone->arena_allocate_region(allocation_size);  // only succeeds once
57#else
58        // try to allocate a region until we get space
59        for (unsigned n = initial_subzone_count; n >= initial_subzone_min_count && !allocation_address; n--) {
60            // size of next attempt
61            allocation_size = managed_size(n);
62            // attempt to allocate data that size
63            allocation_address = allocate_memory(allocation_size, subzone_quantum, VM_MEMORY_MALLOC_SMALL);
64            nzones = n;
65        }
66#endif
67
68        // handle error
69        if (!allocation_address) {
70            error("Can not allocate new region");
71            return NULL;
72        }
73
74        // create region and admin data
75        Region *region = new Region(zone, allocation_address, allocation_size, nzones);
76
77        if (!region) {
78            error("Can not allocate new region");
79            zone->arena_deallocate(allocation_address, allocation_size);
80        }
81
82        return region;
83    }
84
85
86    //
87    // Constructor
88    //
89    Region::Region(Zone *zone, void *address, usword_t size, usword_t nsubzones) {
90        // allocation may fail (and we don't want to use throw)
91        if (!this) return;
92
93        // initialize
94
95        // remember our total size before lopping off pending/stack and mark bit space
96        set_range(address, size);
97        _next = NULL;
98        _zone = zone;
99        _subzone_lock = 0;
100
101        // grab space for use for scanning/stack
102        // We need, worse case, 1 bit per smallest quantum (16 bytes), so this should
103        // have an assert of something like size/allocate_quantum_small/8
104        unsigned long bytes_per_bitmap = nsubzones << subzone_bitmap_bytes_log2;
105        size -= bytes_per_bitmap;
106
107        // we prefer to use the stack, but if it overflows, we have (virtual) space enough
108        // to do a pending bit iterative scan as fallback
109        _scan_space.set_range(displace(address, size), bytes_per_bitmap);
110        // start out as zero length; adding subzones will grow it
111        _pending.set_address(_scan_space.address());
112        _pending.set_size(0);
113
114        // the scanning thread needs exclusive access to the mark bits so they are indpendent
115        // of other 'admin' data.  Reserve enough space for the case of all subzones being of smallest quanta.
116        size -= bytes_per_bitmap;
117        _marks.set_address(displace(address, size));
118        _marks.set_size(0);
119
120        size -= bytes_per_bitmap;
121        _pinned.set_address(displace(address, size));
122        _pinned.set_size(0);
123
124        // track number of subzones
125        _i_subzones = 0;
126        _n_subzones = size >> subzone_quantum_log2;
127        if (_n_subzones != nsubzones) {
128            // we could, in principle, compute the 'tax' of the bitmaps as a percentage and then confirm that
129            // size-tax is a multiple of subzone size.  Easier to pass in the 'nsubzones' and confirm.
130            //printf("size %lx, subzones %d, nsubzones %d\n", size, (int)_n_subzones, (int)nsubzones);
131            error("region: size inconsistent with number of subzones");
132        }
133        _n_quantum = 0;
134    }
135
136
137    //
138    // Destructor
139    //
140    Region::~Region() {
141        // XXX never happens, never will
142    }
143
144
145    //
146    // add_subzone
147    //
148    // Add a new subzone to one of the admin.
149    //
150    bool Region::add_subzone(Admin *admin) {
151        // BEGIN CRITICAL SECTION
152        SpinLock admin_lock(admin->lock());
153
154        // There may have been a race to get here. Verify that the admin has no active subzone
155        // as a quick check that we still need to add one.
156        if (admin->active_subzone()) return true;
157
158        Subzone *subzone = NULL;
159        {
160            SpinLock subzone_lock(&_subzone_lock);
161
162            // if there are no subzones available then not much we can do
163            if (_i_subzones == _n_subzones) return false;
164
165            // Get next subzone
166            subzone = new(subzone_address(_i_subzones++)) Subzone(this, admin, admin->quantum_log2(), _n_quantum);
167
168            // advance quantum count
169            _n_quantum += subzone->allocation_limit();
170
171            // update pending bitmap to total quanta available to be allocated in this region
172            usword_t newBitmapSize = Bitmap::bytes_needed(_n_quantum);
173            _pending.set_size(newBitmapSize);
174            _marks.set_size(newBitmapSize);
175            _pinned.set_size(newBitmapSize);
176        }
177
178        // Add free allocation space to admin
179        admin->set_active_subzone(subzone);
180
181        // let the zone know the subzone is active.
182        _zone->activate_subzone(subzone);
183
184        // END CRITICAL SECTION
185
186        return true;
187    }
188};
189