Rev 1383 | Rev 1403 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 1383 | Rev 1387 | ||
---|---|---|---|
Line 66... | Line 66... | ||
66 | #include <memstr.h> |
66 | #include <memstr.h> |
67 | #include <macros.h> |
67 | #include <macros.h> |
68 | #include <arch.h> |
68 | #include <arch.h> |
69 | #include <errno.h> |
69 | #include <errno.h> |
70 | #include <config.h> |
70 | #include <config.h> |
- | 71 | #include <align.h> |
|
71 | #include <arch/types.h> |
72 | #include <arch/types.h> |
72 | #include <typedefs.h> |
73 | #include <typedefs.h> |
73 | #include <syscall/copy.h> |
74 | #include <syscall/copy.h> |
74 | #include <arch/interrupt.h> |
75 | #include <arch/interrupt.h> |
75 | 76 | ||
Line 89... | Line 90... | ||
89 | 90 | ||
90 | static int area_flags_to_page_flags(int aflags); |
91 | static int area_flags_to_page_flags(int aflags); |
91 | static int get_area_flags(as_area_t *a); |
92 | static int get_area_flags(as_area_t *a); |
92 | static as_area_t *find_area_and_lock(as_t *as, __address va); |
93 | static as_area_t *find_area_and_lock(as_t *as, __address va); |
93 | static bool check_area_conflicts(as_t *as, __address va, size_t size, as_area_t *avoid_area); |
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 | /** Initialize address space subsystem. */ |
98 | /** Initialize address space subsystem. */ |
96 | void as_init(void) |
99 | void as_init(void) |
97 | { |
100 | { |
98 | as_arch_init(); |
101 | as_arch_init(); |
Line 178... | Line 181... | ||
178 | 181 | ||
179 | a->flags = flags; |
182 | a->flags = flags; |
180 | a->attributes = attrs; |
183 | a->attributes = attrs; |
181 | a->pages = SIZE2FRAMES(size); |
184 | a->pages = SIZE2FRAMES(size); |
182 | a->base = base; |
185 | a->base = base; |
- | 186 | btree_create(&a->used_space); |
|
183 | 187 | ||
184 | btree_insert(&as->as_area_btree, base, (void *) a, NULL); |
188 | btree_insert(&as->as_area_btree, base, (void *) a, NULL); |
185 | 189 | ||
186 | mutex_unlock(&as->lock); |
190 | mutex_unlock(&as->lock); |
187 | interrupts_restore(ipl); |
191 | interrupts_restore(ipl); |
Line 942... | Line 946... | ||
942 | } |
946 | } |
943 | interrupts_restore(ipl); |
947 | interrupts_restore(ipl); |
944 | return size; |
948 | return size; |
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 | * Address space related syscalls. |
1324 | * Address space related syscalls. |
949 | */ |
1325 | */ |
950 | 1326 | ||
951 | /** Wrapper for as_area_create(). */ |
1327 | /** Wrapper for as_area_create(). */ |