Changeset 25bf215 in mainline
- Timestamp:
- 2006-05-21T15:15:30Z (19 years ago)
- Branches:
- lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
- Children:
- 2a1803eb
- Parents:
- 7ca8b36b
- Location:
- generic
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
generic/include/mm/as.h
r7ca8b36b r25bf215 35 35 #define AS_AREA_EXEC 4 36 36 #define AS_AREA_DEVICE 8 37 38 37 39 38 #ifdef KERNEL … … 84 83 count_t pages; /**< Size of this area in multiples of PAGE_SIZE. */ 85 84 __address base; /**< Base address of this area. */ 85 btree_t used_space; /**< Map of used space. */ 86 86 }; 87 87 -
generic/src/mm/as.c
r7ca8b36b r25bf215 69 69 #include <errno.h> 70 70 #include <config.h> 71 #include <align.h> 71 72 #include <arch/types.h> 72 73 #include <typedefs.h> … … 92 93 static as_area_t *find_area_and_lock(as_t *as, __address va); 93 94 static bool check_area_conflicts(as_t *as, __address va, size_t size, as_area_t *avoid_area); 95 int used_space_insert(as_area_t *a, __address page, count_t count); 96 int used_space_remove(as_area_t *a, __address page, count_t count); 94 97 95 98 /** Initialize address space subsystem. */ … … 181 184 a->pages = SIZE2FRAMES(size); 182 185 a->base = base; 186 btree_create(&a->used_space); 183 187 184 188 btree_insert(&as->as_area_btree, base, (void *) a, NULL); … … 945 949 } 946 950 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 */ 961 int 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 */ 1183 int 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 1319 error: 1320 panic("Inconsistency detected while removing %d pages of used space from %P.\n", count, page); 1321 } 1322 947 1323 /* 948 1324 * Address space related syscalls.
Note:
See TracChangeset
for help on using the changeset viewer.