source: trunk/kernel/mm/ppm.c @ 9

Last change on this file since 9 was 7, checked in by alain, 7 years ago

Various bugs.

File size: 10.3 KB
Line 
1/*
2 * ppm.c - Per-cluster Physical Pages Manager implementation
3 *
4 * Authors  Ghassan Almaless (2008,2009,2010,2011,2012)
5 *          Alain Greiner    (2016)
6 *
7 * Copyright (c) UPMC Sorbonne Universites
8 *
9 * This file is part of ALMOS-MKH.
10 *
11 * ALMOS-MKH.is free software; you can redistribute it and/or modify it
12 * under the terms of the GNU General Public License as published by
13 * the Free Software Foundation; version 2.0 of the License.
14 *
15 * ALMOS-MKH.is distributed in the hope that it will be useful, but
16 * WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
18 * General Public License for more details.
19 *
20 * You should have received a copy of the GNU General Public License
21 * along with ALMOS-MKH.; if not, write to the Free Software Foundation,
22 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
23 */
24
25#include <almos_config.h>
26#include <hal_types.h>
27#include <hal_special.h>
28#include <printk.h>
29#include <list.h>
30#include <bits.h>
31#include <page.h>
32#include <spinlock.h>
33#include <thread.h>
34#include <cluster.h>
35#include <kmem.h>
36#include <process.h>
37#include <dqdt.h>
38#include <ppm.h>
39
40
41
42////////////////////////////////////////////////
43inline bool_t ppm_page_is_valid( page_t * page )
44{
45    ppm_t    * ppm  = &LOCAL_CLUSTER->ppm;
46        uint32_t   pgnr = (uint32_t)( page - ppm->pages_tbl );
47        return (pgnr <= ppm->pages_nr);
48}
49
50////////////////////////////////////////////
51inline void * ppm_page2base( page_t * page )
52{
53        ppm_t * ppm = &LOCAL_CLUSTER->ppm;
54        return (void*)((page - ppm->pages_tbl) << CONFIG_PPM_PAGE_SHIFT);
55}
56
57////////////////////////////////////////////
58inline page_t * ppm_base2page( void * base ) 
59{
60        ppm_t * ppm = &LOCAL_CLUSTER->ppm;
61        return (ppm->pages_tbl + (((uint32_t)base ) >> CONFIG_PPM_PAGE_SHIFT));
62}
63
64//////////////////////////////////////////
65inline ppn_t ppm_page2ppn( page_t * page )
66{
67        ppm_t  * ppm  = &LOCAL_CLUSTER->ppm;
68        return (ppn_t)( page - ppm->pages_tbl );
69}
70
71/////////////////////////////////////////
72inline page_t * ppm_ppn2page( ppn_t ppn )
73{
74        ppm_t  * ppm  = &LOCAL_CLUSTER->ppm;
75        return &ppm->pages_tbl[ppn];
76}
77
78///////////////////////////////////////
79inline void * ppm_ppn2base( ppn_t ppn )
80{
81        return (void*)( ppn << CONFIG_PPM_PAGE_SHIFT );
82}
83
84////////////////////////////////////////
85inline ppn_t ppm_base2ppn( void * base )
86{
87        return (ppn_t)( (uint32_t)base >> CONFIG_PPM_PAGE_SHIFT );
88}
89
90//////////////////////////////////////////////////
91static void ppm_free_pages_nolock( page_t * page )
92{
93        page_t   * buddy;            // searched buddy page descriptor
94        uint32_t   buddy_index;      // buddy page index
95        page_t   * current;          // current (merged) page descriptor
96        uint32_t   current_index;    // current (merged) page index
97        uint32_t   current_order;    // current (merget) page order
98
99    ppm_t    * ppm         = &LOCAL_CLUSTER->ppm;
100    page_t   * pages_tbl   = ppm->pages_tbl;
101
102    // update released page descriptor flags
103        page_set_flag( page , PG_FREE );
104
105    // search the buddy page descriptor
106    // - merge with current page descriptor if found
107    // - exit to release the current page descriptor if not found
108    current       = page , 
109    current_index = (uint32_t)(page - ppm->pages_tbl);
110        for( current_order = page->order ; 
111         current_order < CONFIG_PPM_MAX_ORDER ;
112         current_order++ )
113    {
114                buddy_index = current_index ^ (1 << current_order);
115                buddy       = pages_tbl + buddy_index;
116   
117                if( !page_is_flag( buddy , PG_FREE ) || (buddy->order != current_order) ) break;
118
119        // remove buddy from free list
120                list_unlink( &buddy->list );
121                ppm->free_pages_nr[current_order] --;
122        ppm->total_free_pages -= (1 << current_order);
123   
124        // merge buddy with current
125                buddy->order = 0;
126                current_index &= buddy_index;
127        }
128 
129    // update merged page descriptor order
130        current        = pages_tbl + current_index;
131        current->order = current_order;
132
133    // insert current in free list
134        list_add_first( &ppm->free_pages_root[current_order] , &current->list );
135        ppm->free_pages_nr[current_order] ++;
136    ppm->total_free_pages += (1 << current_order);
137
138}  // end ppm_free_pages_nolock()
139
140//////////////////////////////
141void ppm_init( ppm_t    * ppm,
142               uint32_t   pages_nr,        // total pages number
143               uint32_t   pages_offset )   // occupied pages
144{
145        uint32_t   i;
146
147    // set signature
148        ppm->signature = PPM_SIGNATURE;
149
150    // initialize lock protecting the free_pages[] array
151        spinlock_init( &ppm->free_lock );
152
153    // initialize free_pages[] array as empty
154        ppm->total_free_pages = 0;
155        for( i = 0 ; i < CONFIG_PPM_MAX_ORDER ; i++ )
156        {
157                list_root_init( &ppm->free_pages_root[i] );
158                ppm->free_pages_nr[i] = 0;
159        }
160
161#if( CONFIG_PPM_DEBUG )
162ppm_print( ppm , "after reset" );
163#endif
164 
165    // initialize dirty_list as empty
166    list_root_init( &ppm->dirty_root );
167
168    // initialize pointer on page descriptors array
169        ppm->pages_tbl = (page_t*)( pages_offset << CONFIG_PPM_PAGE_SHIFT );
170
171    // compute size of pages descriptor array rounded to an integer number of pages
172    uint32_t bytes = ARROUND_UP( pages_nr * sizeof(page_t), CONFIG_PPM_PAGE_SIZE );
173
174    // compute number of pages required to store page descriptor array
175        uint32_t pages_array  = bytes >> CONFIG_PPM_PAGE_SHIFT;
176
177    // compute total number of reserved pages (kernel code & pages_tbl[])
178        uint32_t reserved_pages = pages_offset + pages_array;
179
180        // set pages numbers
181        ppm->pages_nr      = pages_nr;
182    ppm->pages_offset  = reserved_pages;
183
184    // initialises all page descriptors in pages_tbl[]
185        for( i = 0 ; i < pages_nr ; i++ )
186    { 
187        page_init( &ppm->pages_tbl[i] );
188
189        // TODO optimisation : make only a partial init [AG]
190        // complete the initialisation when page is allocated [AG]
191        // ppm->pages_tbl[i].flags = 0;
192    } 
193
194    // - set PG_RESERVED flag for reserved pages (kernel code & pages_tbl[])
195    // - release all other pages to populate the free lists
196        for( i = 0 ; i < reserved_pages ; i++) 
197    {
198        page_set_flag( &ppm->pages_tbl[i] , PG_RESERVED );
199    }
200        for( i = reserved_pages ; i < pages_nr ; i++ )
201        {
202            ppm_free_pages_nolock( &ppm->pages_tbl[i] );
203
204        // TODO optimisation : decompose this enormous set of small pages
205        // to a set big pages with various order values
206        }
207
208    // check consistency
209    ppm_assert_order( ppm );
210
211    kinit_dmsg("\n[INFO] %s : done in cluster %x at cycle %d\n",
212               __FUNCTION__ , local_cxy , hal_time_stamp() );
213
214#if( CONFIG_PPM_DEBUG )
215ppm_print( ppm , "after init" );
216#endif
217   
218} // end ppm_init()
219
220////////////////////////////////////////////
221page_t * ppm_alloc_pages( uint32_t   order )
222{
223    uint32_t   current_order;
224        page_t   * remaining_block;
225        uint32_t   current_size;
226
227    ppm_t    * ppm = &LOCAL_CLUSTER->ppm;
228
229        assert( (ppm->signature == PPM_SIGNATURE) , __FUNCTION__ , "PPM non initialised" );
230
231        assert( (order < CONFIG_PPM_MAX_ORDER) , __FUNCTION__ , "illegal order argument" );
232
233        page_t * block = NULL;
234
235    ppm_dmsg("\n[INFO] %s : enters / order = %d\n",
236             __FUNCTION__ , order );
237
238#if( CONFIG_PPM_DEBUG )
239ppm_print( ppm , "before allocation" );
240#endif
241
242    // take lock protecting free lists
243        spinlock_lock( &ppm->free_lock );
244
245    // find a free block equal or larger to requested size
246        for( current_order = order ; current_order < CONFIG_PPM_MAX_ORDER ; current_order ++ )
247        {
248                if( !list_is_empty( &ppm->free_pages_root[current_order] ) )
249                {
250                        block = LIST_FIRST( &ppm->free_pages_root[current_order] , page_t , list );
251                        list_unlink( &block->list );
252                        break;
253                }
254        }
255
256        if( block == NULL ) // return failure
257        {
258        // release lock protecting free lists
259            spinlock_unlock( &ppm->free_lock );
260
261        return NULL;
262    }
263 
264    // update free-lists after removing a block
265        ppm->total_free_pages -= (1 << current_order);
266        ppm->free_pages_nr[current_order] --; 
267        current_size = (1 << current_order);
268
269    // split the removed block in smaller sub-blocks if required
270    // and update the free-lists accordingly
271        while( current_order > order )
272        {
273                current_order --;
274                current_size >>= 1;
275   
276                remaining_block = block + current_size;
277                remaining_block->order = current_order;
278
279                list_add_first( &ppm->free_pages_root[current_order] , &remaining_block->list );
280                ppm->free_pages_nr[current_order] ++;
281        ppm->total_free_pages += (1 << current_order);
282        }
283 
284    // update page descriptor
285    page_clear_flag( block , PG_FREE );
286        page_refcount_up( block );
287        block->order = order;
288
289    // release lock protecting free lists
290        spinlock_unlock( &ppm->free_lock );
291 
292    ppm_dmsg("\n[INFO] %s : base = %x / order = %d\n",
293             __FUNCTION__ , (uint32_t)ppm_page2base( block ) , order );
294
295#if CONFIG_PPM_DEBUG
296ppm_print( ppm , "after allocation" );
297#endif
298
299        return block;
300}  // end pmm_alloc-pages()
301
302
303////////////////////////////////////
304void ppm_free_pages( page_t * page )
305{
306        ppm_t * ppm = &LOCAL_CLUSTER->ppm;
307 
308    // get lock protecting free_pages[] array
309        spinlock_lock( &ppm->free_lock );
310
311        ppm_free_pages_nolock( page ); 
312
313    // release lock protecting free_pages[] array
314        spinlock_unlock( &ppm->free_lock );
315}
316
317////////////////////////////
318void ppm_print( ppm_t * ppm,
319                char  * string )
320{
321        uint32_t       order;
322        list_entry_t * iter;
323        page_t       * page;
324
325    // get lock protecting free lists
326        spinlock_lock( &ppm->free_lock );
327
328        printk("\n***  PPM state in cluster %x %s : pages = %d / offset = %d / free = %d ***\n",
329               local_cxy , string , ppm->pages_nr , ppm->pages_offset , ppm->total_free_pages ); 
330       
331        for( order = 0 ; order < CONFIG_PPM_MAX_ORDER ; order++ )
332        {
333                printk("- order = %d / free_pages = %d  [",
334               order , ppm->free_pages_nr[order] );
335               
336                LIST_FOREACH( &ppm->free_pages_root[order] , iter )
337                {
338                        page = LIST_ELEMENT( iter , page_t , list );
339                        printk("%d," , page - ppm->pages_tbl );
340                }
341   
342                printk("]\n", NULL );
343        }
344
345    // release lock protecting free lists
346        spinlock_unlock( &ppm->free_lock );
347
348}  // end ppm_print()
349 
350//////////////////////////u/////////
351void ppm_assert_order( ppm_t * ppm )
352{
353        uint32_t       order;
354        list_entry_t * iter;
355        page_t       * page;
356       
357        for(order=0; order < CONFIG_PPM_MAX_ORDER; order++)
358        {
359                if( list_is_empty( &ppm->free_pages_root[order] ) ) continue;
360               
361                LIST_FOREACH( &ppm->free_pages_root[order] , iter )
362                {
363                        page = LIST_ELEMENT( iter , page_t , list );
364
365                        assert( (page->order == order) , __FUNCTION__ , "PPM inconsistency" );
366                }
367        }
368
369}  // end ppm_assert_order()
370
Note: See TracBrowser for help on using the repository browser.