Changeset 25bf215 in mainline


Ignore:
Timestamp:
2006-05-21T15:15:30Z (19 years ago)
Author:
Jakub Jermar <jakub@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
2a1803eb
Parents:
7ca8b36b
Message:

Add used_space_insert() and used_space_remove().
These are the alpha versions of functions that
will help to map used and unused portions of address
space areas. Currently unused, but many as_area operations
will be more efficient when the used space B+tree map
is used.

Location:
generic
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • generic/include/mm/as.h

    r7ca8b36b r25bf215  
    3535#define AS_AREA_EXEC    4
    3636#define AS_AREA_DEVICE  8
    37 
    3837
    3938#ifdef KERNEL
     
    8483        count_t pages;          /**< Size of this area in multiples of PAGE_SIZE. */
    8584        __address base;         /**< Base address of this area. */
     85        btree_t used_space;     /**< Map of used space. */
    8686};
    8787
  • generic/src/mm/as.c

    r7ca8b36b r25bf215  
    6969#include <errno.h>
    7070#include <config.h>
     71#include <align.h>
    7172#include <arch/types.h>
    7273#include <typedefs.h>
     
    9293static as_area_t *find_area_and_lock(as_t *as, __address va);
    9394static bool check_area_conflicts(as_t *as, __address va, size_t size, as_area_t *avoid_area);
     95int used_space_insert(as_area_t *a, __address page, count_t count);
     96int used_space_remove(as_area_t *a, __address page, count_t count);
    9497
    9598/** Initialize address space subsystem. */
     
    181184        a->pages = SIZE2FRAMES(size);
    182185        a->base = base;
     186        btree_create(&a->used_space);
    183187       
    184188        btree_insert(&as->as_area_btree, base, (void *) a, NULL);
     
    945949}
    946950
     951/** Mark portion of address space area as used.
     952 *
     953 * The address space area must be already locked.
     954 *
     955 * @param a Address space area.
     956 * @param page First page to be marked.
     957 * @param count Number of page to be marked.
     958 *
     959 * @return 0 on failure and 1 on success.
     960 */
     961int used_space_insert(as_area_t *a, __address page, count_t count)
     962{
     963        btree_node_t *leaf, *node;
     964        count_t pages;
     965        int i;
     966
     967        ASSERT(page == ALIGN_DOWN(page, PAGE_SIZE));
     968        ASSERT(count);
     969
     970        pages = (count_t) btree_search(&a->used_space, page, &leaf);
     971        if (pages) {
     972                /*
     973                 * We hit the beginning of some used space.
     974                 */
     975                return 0;
     976        }
     977
     978        node = btree_leaf_node_left_neighbour(&a->used_space, leaf);
     979        if (node) {
     980                __address left_pg = node->key[node->keys - 1], right_pg = leaf->key[0];
     981                count_t left_cnt = (count_t) node->value[node->keys - 1], right_cnt = (count_t) leaf->value[0];
     982               
     983                /*
     984                 * Examine the possibility that the interval fits
     985                 * somewhere between the rightmost interval of
     986                 * the left neigbour and the first interval of the leaf.
     987                 */
     988                 
     989                if (page >= right_pg) {
     990                        /* Do nothing. */
     991                } else if (overlaps(page, count*PAGE_SIZE, left_pg, left_cnt*PAGE_SIZE)) {
     992                        /* The interval intersects with the left interval. */
     993                        return 0;
     994                } else if (overlaps(page, count*PAGE_SIZE, right_pg, right_cnt*PAGE_SIZE)) {
     995                        /* The interval intersects with the right interval. */
     996                        return 0;                       
     997                } else if ((page == left_pg + left_cnt*PAGE_SIZE) && (page + count*PAGE_SIZE == right_pg)) {
     998                        /* The interval can be added by merging the two already present intervals. */
     999                        node->value[node->keys - 1] += (count_t) count + right_cnt;
     1000                        btree_remove(&a->used_space, right_pg, leaf);
     1001                        return 1;
     1002                } else if (page == left_pg + left_cnt*PAGE_SIZE) {
     1003                        /* The interval can be added by simply growing the left interval. */
     1004                        node->value[node->keys - 1] += (count_t) count;
     1005                        return 1;
     1006                } else if (page + count*PAGE_SIZE == right_pg) {
     1007                        /*
     1008                         * The interval can be addded by simply moving base of the right
     1009                         * interval down and increasing its size accordingly.
     1010                         */
     1011                        leaf->value[0] += (count_t) count;
     1012                        leaf->key[0] = page;
     1013                        return 1;
     1014                } else {
     1015                        /*
     1016                         * The interval is between both neigbouring intervals,
     1017                         * but cannot be merged with any of them.
     1018                         */
     1019                        btree_insert(&a->used_space, page, (void *) count, leaf);
     1020                        return 1;
     1021                }
     1022        } else if (page < leaf->key[0]) {
     1023                __address right_pg = leaf->key[0];
     1024                count_t right_cnt = (count_t) leaf->value[0];
     1025       
     1026                /*
     1027                 * Investigate the border case in which the left neighbour does not
     1028                 * exist but the interval fits from the left.
     1029                 */
     1030                 
     1031                if (overlaps(page, count*PAGE_SIZE, right_pg, right_cnt*PAGE_SIZE)) {
     1032                        /* The interval intersects with the right interval. */
     1033                        return 0;
     1034                } else if (page + count*PAGE_SIZE == right_pg) {
     1035                        /*
     1036                         * The interval can be added by moving the base of the right interval down
     1037                         * and increasing its size accordingly.
     1038                         */
     1039                        leaf->key[0] = page;
     1040                        leaf->value[0] += (count_t) count;
     1041                        return 1;
     1042                } else {
     1043                        /*
     1044                         * The interval doesn't adjoin with the right interval.
     1045                         * It must be added individually.
     1046                         */
     1047                        btree_insert(&a->used_space, page, (void *) count, leaf);
     1048                        return 1;
     1049                }
     1050        }
     1051
     1052        node = btree_leaf_node_right_neighbour(&a->used_space, leaf);
     1053        if (node) {
     1054                __address left_pg = leaf->key[leaf->keys - 1], right_pg = node->key[0];
     1055                count_t left_cnt = (count_t) leaf->value[leaf->keys - 1], right_cnt = (count_t) node->value[0];
     1056               
     1057                /*
     1058                 * Examine the possibility that the interval fits
     1059                 * somewhere between the leftmost interval of
     1060                 * the right neigbour and the last interval of the leaf.
     1061                 */
     1062
     1063                if (page < left_pg) {
     1064                        /* Do nothing. */
     1065                } else if (overlaps(page, count*PAGE_SIZE, left_pg, left_cnt*PAGE_SIZE)) {
     1066                        /* The interval intersects with the left interval. */
     1067                        return 0;
     1068                } else if (overlaps(page, count*PAGE_SIZE, right_pg, right_cnt*PAGE_SIZE)) {
     1069                        /* The interval intersects with the right interval. */
     1070                        return 0;                       
     1071                } else if ((page == left_pg + left_cnt*PAGE_SIZE) && (page + count*PAGE_SIZE == right_pg)) {
     1072                        /* The interval can be added by merging the two already present intervals. */
     1073                        leaf->value[leaf->keys - 1] += (count_t) count + right_cnt;
     1074                        btree_remove(&a->used_space, right_pg, node);
     1075                        return 1;
     1076                } else if (page == left_pg + left_cnt*PAGE_SIZE) {
     1077                        /* The interval can be added by simply growing the left interval. */
     1078                        leaf->value[leaf->keys - 1] += (count_t) count;
     1079                        return 1;
     1080                } else if (page + count*PAGE_SIZE == right_pg) {
     1081                        /*
     1082                         * The interval can be addded by simply moving base of the right
     1083                         * interval down and increasing its size accordingly.
     1084                         */
     1085                        node->value[0] += (count_t) count;
     1086                        node->key[0] = page;
     1087                        return 1;
     1088                } else {
     1089                        /*
     1090                         * The interval is between both neigbouring intervals,
     1091                         * but cannot be merged with any of them.
     1092                         */
     1093                        btree_insert(&a->used_space, page, (void *) count, leaf);
     1094                        return 1;
     1095                }
     1096        } else if (page >= leaf->key[leaf->keys - 1]) {
     1097                __address left_pg = leaf->key[leaf->keys - 1];
     1098                count_t left_cnt = (count_t) leaf->value[leaf->keys - 1];
     1099       
     1100                /*
     1101                 * Investigate the border case in which the right neighbour does not
     1102                 * exist but the interval fits from the right.
     1103                 */
     1104                 
     1105                if (overlaps(page, count*PAGE_SIZE, left_pg, left_cnt*PAGE_SIZE)) {
     1106                        /* The interval intersects with the right interval. */
     1107                        return 0;
     1108                } else if (left_pg + left_cnt*PAGE_SIZE == page) {
     1109                        /* The interval can be added by growing the left interval. */
     1110                        leaf->value[leaf->keys - 1] += (count_t) count;
     1111                        return 1;
     1112                } else {
     1113                        /*
     1114                         * The interval doesn't adjoin with the left interval.
     1115                         * It must be added individually.
     1116                         */
     1117                        btree_insert(&a->used_space, page, (void *) count, leaf);
     1118                        return 1;
     1119                }
     1120        }
     1121       
     1122        /*
     1123         * Note that if the algorithm made it thus far, the interval can fit only
     1124         * between two other intervals of the leaf. The two border cases were already
     1125         * resolved.
     1126         */
     1127        for (i = 1; i < leaf->keys; i++) {
     1128                if (page < leaf->key[i]) {
     1129                        __address left_pg = leaf->key[i - 1], right_pg = leaf->key[i];
     1130                        count_t left_cnt = (count_t) leaf->value[i - 1], right_cnt = (count_t) leaf->value[i];
     1131
     1132                        /*
     1133                         * The interval fits between left_pg and right_pg.
     1134                         */
     1135
     1136                        if (overlaps(page, count*PAGE_SIZE, left_pg, left_cnt*PAGE_SIZE)) {
     1137                                /* The interval intersects with the left interval. */
     1138                                return 0;
     1139                        } else if (overlaps(page, count*PAGE_SIZE, right_pg, right_cnt*PAGE_SIZE)) {
     1140                                /* The interval intersects with the right interval. */
     1141                                return 0;                       
     1142                        } else if ((page == left_pg + left_cnt*PAGE_SIZE) && (page + count*PAGE_SIZE == right_pg)) {
     1143                                /* The interval can be added by merging the two already present intervals. */
     1144                                leaf->value[i - 1] += (count_t) count + right_cnt;
     1145                                btree_remove(&a->used_space, right_pg, leaf);
     1146                                return 1;
     1147                        } else if (page == left_pg + left_cnt*PAGE_SIZE) {
     1148                                /* The interval can be added by simply growing the left interval. */
     1149                                leaf->value[i - 1] += (count_t) count;
     1150                                return 1;
     1151                        } else if (page + count*PAGE_SIZE == right_pg) {
     1152                                /*
     1153                                 * The interval can be addded by simply moving base of the right
     1154                                 * interval down and increasing its size accordingly.
     1155                                 */
     1156                                leaf->value[i] += (count_t) count;
     1157                                leaf->key[i] = page;
     1158                                return 1;
     1159                        } else {
     1160                                /*
     1161                                 * The interval is between both neigbouring intervals,
     1162                                 * but cannot be merged with any of them.
     1163                                 */
     1164                                btree_insert(&a->used_space, page, (void *) count, leaf);
     1165                                return 1;
     1166                        }
     1167                }
     1168        }
     1169
     1170        panic("Inconsistency detected while adding %d pages of used space at %P.\n", count, page);
     1171}
     1172
     1173/** Mark portion of address space area as unused.
     1174 *
     1175 * The address space area must be already locked.
     1176 *
     1177 * @param a Address space area.
     1178 * @param page First page to be marked.
     1179 * @param count Number of page to be marked.
     1180 *
     1181 * @return 0 on failure and 1 on success.
     1182 */
     1183int used_space_remove(as_area_t *a, __address page, count_t count)
     1184{
     1185        btree_node_t *leaf, *node;
     1186        count_t pages;
     1187        int i;
     1188
     1189        ASSERT(page == ALIGN_DOWN(page, PAGE_SIZE));
     1190        ASSERT(count);
     1191
     1192        pages = (count_t) btree_search(&a->used_space, page, &leaf);
     1193        if (pages) {
     1194                /*
     1195                 * We are lucky, page is the beginning of some interval.
     1196                 */
     1197                if (count > pages) {
     1198                        return 0;
     1199                } else if (count == pages) {
     1200                        btree_remove(&a->used_space, page, leaf);
     1201                } else {
     1202                        /*
     1203                         * Find the respective interval.
     1204                         * Decrease its size and relocate its start address.
     1205                         */
     1206                        for (i = 0; i < leaf->keys; i++) {
     1207                                if (leaf->key[i] == page) {
     1208                                        leaf->key[i] += count*PAGE_SIZE;
     1209                                        leaf->value[i] -= (count_t) count;
     1210                                        return 1;
     1211                                }
     1212                        }
     1213                        goto error;
     1214                }
     1215        }
     1216
     1217        node = btree_leaf_node_left_neighbour(&a->used_space, leaf);
     1218        if (node && page < leaf->key[0]) {
     1219                __address left_pg = node->key[node->keys - 1];
     1220                count_t left_cnt = (count_t) node->value[node->keys - 1];
     1221
     1222                if (overlaps(left_pg, left_cnt*PAGE_SIZE, page, count*PAGE_SIZE)) {
     1223                        if (page + count*PAGE_SIZE == left_pg + left_cnt*PAGE_SIZE) {
     1224                                /*
     1225                                 * The interval is contained in the rightmost interval
     1226                                 * of the left neighbour and can be removed by
     1227                                 * updating the size of the bigger interval.
     1228                                 */
     1229                                node->value[node->keys - 1] -= (count_t) count;
     1230                                return 1;
     1231                        } else if (page + count*PAGE_SIZE < left_pg + left_cnt*PAGE_SIZE) {
     1232                                count_t new_cnt = (left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE);
     1233                               
     1234                                /*
     1235                                 * The interval is contained in the rightmost interval
     1236                                 * of the left neighbour but its removal requires
     1237                                 * both updating the size of the original interval and
     1238                                 * also inserting a new interval.
     1239                                 */
     1240                                node->value[node->keys - 1] -= (count_t) count + new_cnt;
     1241                                btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf);
     1242                                return 1;
     1243                        }
     1244                }
     1245                return 0;
     1246        } else if (page < leaf->key[0]) {
     1247                return 0;
     1248        }
     1249       
     1250        if (page > leaf->key[leaf->keys - 1]) {
     1251                __address left_pg = leaf->key[leaf->keys - 1];
     1252                count_t left_cnt = (count_t) leaf->value[leaf->keys - 1];
     1253
     1254                if (overlaps(left_pg, left_cnt*PAGE_SIZE, page, count*PAGE_SIZE)) {
     1255                        if (page + count*PAGE_SIZE == left_pg + left_cnt*PAGE_SIZE) {
     1256                                /*
     1257                                 * The interval is contained in the rightmost interval
     1258                                 * of the leaf and can be removed by updating the size
     1259                                 * of the bigger interval.
     1260                                 */
     1261                                leaf->value[leaf->keys - 1] -= (count_t) count;
     1262                                return 1;
     1263                        } else if (page + count*PAGE_SIZE < left_pg + left_cnt*PAGE_SIZE) {
     1264                                count_t new_cnt = (left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE);
     1265                               
     1266                                /*
     1267                                 * The interval is contained in the rightmost interval
     1268                                 * of the leaf but its removal requires both updating
     1269                                 * the size of the original interval and
     1270                                 * also inserting a new interval.
     1271                                 */
     1272                                leaf->value[leaf->keys - 1] -= (count_t) count + new_cnt;
     1273                                btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf);
     1274                                return 1;
     1275                        }
     1276                }
     1277                return 0;
     1278        }       
     1279       
     1280        /*
     1281         * The border cases have been already resolved.
     1282         * Now the interval can be only between intervals of the leaf.
     1283         */
     1284        for (i = 1; i < leaf->keys - 1; i++) {
     1285                if (page < leaf->key[i]) {
     1286                        __address left_pg = leaf->key[i - 1];
     1287                        count_t left_cnt = (count_t) leaf->value[i - 1];
     1288
     1289                        /*
     1290                         * Now the interval is between intervals corresponding to (i - 1) and i.
     1291                         */
     1292                        if (overlaps(left_pg, left_cnt*PAGE_SIZE, page, count*PAGE_SIZE)) {
     1293                                if (page + count*PAGE_SIZE == left_pg + left_cnt*PAGE_SIZE) {
     1294                                        /*
     1295                                        * The interval is contained in the interval (i - 1)
     1296                                         * of the leaf and can be removed by updating the size
     1297                                         * of the bigger interval.
     1298                                         */
     1299                                        leaf->value[i - 1] -= (count_t) count;
     1300                                        return 1;
     1301                                } else if (page + count*PAGE_SIZE < left_pg + left_cnt*PAGE_SIZE) {
     1302                                        count_t new_cnt = (left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE);
     1303                               
     1304                                        /*
     1305                                         * The interval is contained in the interval (i - 1)
     1306                                         * of the leaf but its removal requires both updating
     1307                                         * the size of the original interval and
     1308                                         * also inserting a new interval.
     1309                                         */
     1310                                        leaf->value[i - 1] -= (count_t) count + new_cnt;
     1311                                        btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf);
     1312                                        return 1;
     1313                                }
     1314                        }
     1315                        return 0;
     1316                }
     1317        }
     1318
     1319error:
     1320        panic("Inconsistency detected while removing %d pages of used space from %P.\n", count, page);
     1321}
     1322
    9471323/*
    9481324 * Address space related syscalls.
Note: See TracChangeset for help on using the changeset viewer.