Fork us on GitHub Follow us on Facebook Follow us on Twitter

Changeset b4e59b3 in mainline


Ignore:
Timestamp:
2011-12-05T23:17:46Z (10 years ago)
Author:
Jakub Jermar <jakub@…>
Branches:
lfn, master
Children:
12cb03d
Parents:
961c0484
Message:

WIP: Implement ra_free().

Location:
kernel/generic
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • kernel/generic/include/lib/ra.h

    r961c0484 rb4e59b3  
    5858} ra_span_t;
    5959
     60#define RA_SEGMENT_FREE         1
     61
    6062/*
    6163 * We would like to achieve a good ratio of the size of one unit of the
     
    7072
    7173        uintptr_t base;         /**< Segment base. */
     74        uint8_t flags;          /**< Segment flags. */
    7275} ra_segment_t;
    7376
  • kernel/generic/src/lib/ra.c

    r961c0484 rb4e59b3  
    5454#include <macros.h>
    5555
    56 /*
    57  * The last segment on the segment list will be a special sentinel segment which
    58  * is neither in any free list nor in the used segment hash.
    59  */
    60 #define IS_LAST_SEG(seg)        (!(seg)->fu_link.next)
    61 
    6256static hash_table_operations_t used_ops = {
    6357        .hash = NULL,
     
    7165        ra_segment_t *nextseg;
    7266
    73         ASSERT(!IS_LAST_SEG(seg));
    74 
    7567        nextseg = list_get_instance(seg->segment_link.next, ra_segment_t,
    7668            segment_link);
     
    9082
    9183        seg->base = base;
     84        seg->flags = 0;
    9285
    9386        return seg;
     
    129122                return NULL;
    130123        }
     124        seg->flags = RA_SEGMENT_FREE;
    131125
    132126        /*
     
    144138                return NULL;
    145139        }
    146         /* Make sure we have NULL here so that we can recognize the sentinel. */
    147         lastseg->fu_link.next = NULL;
    148140
    149141        link_initialize(&span->span_link);
     
    238230                seg = list_get_instance(list_first(&span->free[order]),
    239231                    ra_segment_t, fu_link);
     232
     233                ASSERT(seg->flags & RA_SEGMENT_FREE);
    240234
    241235                /*
     
    251245                                break;
    252246                        }
     247                        pred->flags |= RA_SEGMENT_FREE;
    253248                }
    254249                newbase = ALIGN_UP(seg->base, align);
     
    265260                                break;
    266261                        }
     262                        succ->flags |= RA_SEGMENT_FREE;
    267263                }
    268264               
     
    289285                list_remove(&seg->fu_link);
    290286                seg->base = newbase;
     287                seg->flags &= ~RA_SEGMENT_FREE;
    291288
    292289                /* Hash-in the segment into the used hash. */
     
    302299static void ra_span_free(ra_span_t *span, size_t base, size_t size)
    303300{
     301        sysarg_t key = base;
     302        link_t *link;
     303        ra_segment_t *seg;
     304        ra_segment_t *pred;
     305        ra_segment_t *succ;
     306        size_t order;
     307
     308        /*
     309         * Locate the segment in the used hash table.
     310         */
     311        link = hash_table_find(&span->used, &key);
     312        if (!link) {
     313                panic("Freeing segment which is not known to be used (base=%"
     314                    PRIxn ", size=%" PRIdn ").", base, size);
     315        }
     316        seg = hash_table_get_instance(link, ra_segment_t, fu_link);
     317
     318        /*
     319         * Hash out the segment.
     320         */
     321        hash_table_remove(&span->used, &key, 1);
     322
     323        ASSERT(!(seg->flags & RA_SEGMENT_FREE));
     324        ASSERT(seg->base == base);
     325        ASSERT(ra_segment_size_get(seg) == size);
     326
     327        /*
     328         * Check whether the segment can be coalesced with its left neighbor.
     329         */
     330        if (list_first(&span->segments) != &seg->segment_link) {
     331                pred = hash_table_get_instance(seg->segment_link.prev,
     332                    ra_segment_t, segment_link);
     333
     334                ASSERT(pred->base < seg->base);
     335
     336                if (pred->flags & RA_SEGMENT_FREE) {
     337                        /*
     338                         * The segment can be coalesced with its predecessor.
     339                         * Remove the predecessor from the free and segment
     340                         * lists, rebase the segment and throw the predecessor
     341                         * away.
     342                         */
     343                        list_remove(&pred->fu_link);
     344                        list_remove(&pred->segment_link);
     345                        seg->base = pred->base;
     346                        ra_segment_destroy(pred);
     347                }
     348        }
     349
     350        /*
     351         * Check whether the segment can be coalesced with its right neighbor.
     352         */
     353        succ = hash_table_get_instance(seg->segment_link.next, ra_segment_t,
     354            segment_link);
     355        ASSERT(succ->base > seg->base);
     356        if (succ->flags & RA_SEGMENT_FREE) {
     357                /*
     358                 * The segment can be coalesced with its successor.
     359                 * Remove the successor from the free and segment lists
     360                 * and throw it away.
     361                 */
     362                list_remove(&succ->fu_link);
     363                list_remove(&succ->segment_link);
     364                ra_segment_destroy(succ);
     365        }
     366
     367        /* Put the segment on the appropriate free list. */
     368        seg->flags |= RA_SEGMENT_FREE;
     369        order = fnzb(ra_segment_size_get(seg));
     370        list_append(&seg->fu_link, &span->free[order]);
    304371}
    305372
Note: See TracChangeset for help on using the changeset viewer.