1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700 1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711 1712 1713 1714 1715 1716 1717 1718 1719 1720 1721 1722 1723 1724 1725 1726 1727 1728 1729 1730 1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750 1751 1752 1753 1754 1755 1756 1757 1758 1759 1760 1761 1762 1763 1764 1765 1766 1767 1768 1769 1770 1771 1772 1773 1774 1775 1776 1777 1778 1779 1780 1781 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795 1796 1797 1798 1799 1800 1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890 1891 1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945 1946 1947 1948 1949 1950 1951 1952 1953 1954 1955 1956 1957 1958 1959 1960 1961 1962 1963 1964 1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034 2035 2036 2037 2038 2039 2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052 2053 2054 2055 2056 2057 2058 2059 2060 2061 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081 2082 2083 2084 2085 2086 2087 2088 2089 2090 2091 2092 2093 2094 2095 2096 2097 2098 2099 2100 2101 2102 2103 2104 2105 2106 2107 2108 2109 2110 2111 2112 2113 2114 2115 2116 2117 2118 2119 2120 2121 2122 2123 2124 2125 2126 2127 2128 2129 2130 2131 2132 2133 2134 2135 2136 2137 2138 2139 2140 2141 2142 2143 2144 2145 2146 2147 2148 2149 2150 2151 2152 2153 2154 2155 2156 2157 2158 2159 2160 2161 2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 2175 2176 2177 2178 2179 2180 2181 2182 2183 2184 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206 2207 2208 2209 2210 2211 2212 2213 2214 2215 2216 2217 2218 2219 2220 2221 2222 2223 2224 2225 2226 2227 2228 2229 2230 2231 2232 2233 2234 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266 2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278 2279 2280 2281 2282 2283 2284 2285 2286 2287 2288 2289 2290 2291 2292 2293 2294 2295 2296 2297 2298 2299 2300 2301 2302 2303 2304 2305 2306 2307 2308 2309 2310 2311 2312 2313 2314 2315 2316 2317 2318 2319 2320 2321 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 2378 2379 2380 2381 2382 2383 2384 2385 2386 2387 2388 2389 2390 2391 2392 2393 2394 2395 2396 2397 2398 2399 2400 2401 2402 2403 2404 2405 2406 2407 2408 2409 2410 2411 2412 2413 2414 2415 2416 2417 2418 2419 2420 2421 2422 2423 2424 2425 2426 2427 2428 2429 2430 2431 2432 2433 2434 2435 2436 2437 2438 2439 2440 2441 2442 2443 2444 2445 2446 2447 2448 2449 2450 2451 2452 2453 2454 2455 2456 2457 2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468 2469 2470 2471 2472 2473 2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485 2486 2487 2488 2489 2490 2491 2492 2493 2494 2495 2496 2497 2498 2499 2500 2501 2502 2503 2504 2505 2506 2507 2508 2509 2510 2511 2512 2513 2514 2515 2516 2517 2518 2519 2520 2521 2522 2523 2524 2525 2526 2527 2528 2529 2530 2531 2532 2533 2534 2535 2536 2537 2538 2539 2540 2541 2542 2543 2544 2545 2546 2547 2548 2549 2550 2551 2552 2553 2554 2555 2556 2557 2558 2559 2560 2561 2562 2563 2564 2565 2566 2567 2568 2569 2570 2571 2572 2573 2574 2575 2576 2577 2578 2579 2580 2581 2582 2583 2584 2585 2586 2587 2588 2589 2590 2591 2592 2593 2594 2595 2596 2597 2598 2599 2600 2601 2602 2603 2604 2605 2606 2607 2608 2609 2610 2611 2612 2613 2614 2615 2616 2617 2618 2619 2620 2621 2622 2623 2624 2625 2626 2627 2628 2629 2630 2631 2632 2633 2634 2635 2636 2637 2638 2639 2640 2641 2642 2643 2644 2645 2646 2647 2648 2649 2650 2651 2652 2653 2654 2655 2656 2657 2658 2659 2660 2661 2662 2663 2664 2665 2666 2667 2668 2669 2670 2671 2672 2673 2674 2675 2676 2677 2678 2679 2680 2681 2682 2683 2684 2685
|
// Copyright 2011 the V8 project authors. All rights reserved.
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
// * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following
// disclaimer in the documentation and/or other materials provided
// with the distribution.
// * Neither the name of Google Inc. nor the names of its
// contributors may be used to endorse or promote products derived
// from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#ifndef V8_SPACES_H_
#define V8_SPACES_H_
#include "allocation.h"
#include "hashmap.h"
#include "list.h"
#include "log.h"
namespace v8 {
namespace internal {
class Isolate;
// -----------------------------------------------------------------------------
// Heap structures:
//
// A JS heap consists of a young generation, an old generation, and a large
// object space. The young generation is divided into two semispaces. A
// scavenger implements Cheney's copying algorithm. The old generation is
// separated into a map space and an old object space. The map space contains
// all (and only) map objects, the rest of old objects go into the old space.
// The old generation is collected by a mark-sweep-compact collector.
//
// The semispaces of the young generation are contiguous. The old and map
// spaces consists of a list of pages. A page has a page header and an object
// area.
//
// There is a separate large object space for objects larger than
// Page::kMaxHeapObjectSize, so that they do not have to move during
// collection. The large object space is paged. Pages in large object space
// may be larger than the page size.
//
// A store-buffer based write barrier is used to keep track of intergenerational
// references. See store-buffer.h.
//
// During scavenges and mark-sweep collections we sometimes (after a store
// buffer overflow) iterate intergenerational pointers without decoding heap
// object maps so if the page belongs to old pointer space or large object
// space it is essential to guarantee that the page does not contain any
// garbage pointers to new space: every pointer aligned word which satisfies
// the Heap::InNewSpace() predicate must be a pointer to a live heap object in
// new space. Thus objects in old pointer and large object spaces should have a
// special layout (e.g. no bare integer fields). This requirement does not
// apply to map space which is iterated in a special fashion. However we still
// require pointer fields of dead maps to be cleaned.
//
// To enable lazy cleaning of old space pages we can mark chunks of the page
// as being garbage. Garbage sections are marked with a special map. These
// sections are skipped when scanning the page, even if we are otherwise
// scanning without regard for object boundaries. Garbage sections are chained
// together to form a free list after a GC. Garbage sections created outside
// of GCs by object trunctation etc. may not be in the free list chain. Very
// small free spaces are ignored, they need only be cleaned of bogus pointers
// into new space.
//
// Each page may have up to one special garbage section. The start of this
// section is denoted by the top field in the space. The end of the section
// is denoted by the limit field in the space. This special garbage section
// is not marked with a free space map in the data. The point of this section
// is to enable linear allocation without having to constantly update the byte
// array every time the top field is updated and a new object is created. The
// special garbage section is not in the chain of garbage sections.
//
// Since the top and limit fields are in the space, not the page, only one page
// has a special garbage section, and if the top and limit are equal then there
// is no special garbage section.
// Some assertion macros used in the debugging mode.
#define ASSERT_PAGE_ALIGNED(address) \
ASSERT((OffsetFrom(address) & Page::kPageAlignmentMask) == 0)
#define ASSERT_OBJECT_ALIGNED(address) \
ASSERT((OffsetFrom(address) & kObjectAlignmentMask) == 0)
#define ASSERT_OBJECT_SIZE(size) \
ASSERT((0 < size) && (size <= Page::kMaxNonCodeHeapObjectSize))
#define ASSERT_PAGE_OFFSET(offset) \
ASSERT((Page::kObjectStartOffset <= offset) \
&& (offset <= Page::kPageSize))
#define ASSERT_MAP_PAGE_INDEX(index) \
ASSERT((0 <= index) && (index <= MapSpace::kMaxMapPageIndex))
class PagedSpace;
class MemoryAllocator;
class AllocationInfo;
class Space;
class FreeList;
class MemoryChunk;
class MarkBit {
public:
typedef uint32_t CellType;
inline MarkBit(CellType* cell, CellType mask, bool data_only)
: cell_(cell), mask_(mask), data_only_(data_only) { }
inline CellType* cell() { return cell_; }
inline CellType mask() { return mask_; }
#ifdef DEBUG
bool operator==(const MarkBit& other) {
return cell_ == other.cell_ && mask_ == other.mask_;
}
#endif
inline void Set() { *cell_ |= mask_; }
inline bool Get() { return (*cell_ & mask_) != 0; }
inline void Clear() { *cell_ &= ~mask_; }
inline bool data_only() { return data_only_; }
inline MarkBit Next() {
CellType new_mask = mask_ << 1;
if (new_mask == 0) {
return MarkBit(cell_ + 1, 1, data_only_);
} else {
return MarkBit(cell_, new_mask, data_only_);
}
}
private:
CellType* cell_;
CellType mask_;
// This boolean indicates that the object is in a data-only space with no
// pointers. This enables some optimizations when marking.
// It is expected that this field is inlined and turned into control flow
// at the place where the MarkBit object is created.
bool data_only_;
};
// Bitmap is a sequence of cells each containing fixed number of bits.
class Bitmap {
public:
static const uint32_t kBitsPerCell = 32;
static const uint32_t kBitsPerCellLog2 = 5;
static const uint32_t kBitIndexMask = kBitsPerCell - 1;
static const uint32_t kBytesPerCell = kBitsPerCell / kBitsPerByte;
static const uint32_t kBytesPerCellLog2 = kBitsPerCellLog2 - kBitsPerByteLog2;
static const size_t kLength =
(1 << kPageSizeBits) >> (kPointerSizeLog2);
static const size_t kSize =
(1 << kPageSizeBits) >> (kPointerSizeLog2 + kBitsPerByteLog2);
static int CellsForLength(int length) {
return (length + kBitsPerCell - 1) >> kBitsPerCellLog2;
}
int CellsCount() {
return CellsForLength(kLength);
}
static int SizeFor(int cells_count) {
return sizeof(MarkBit::CellType) * cells_count;
}
INLINE(static uint32_t IndexToCell(uint32_t index)) {
return index >> kBitsPerCellLog2;
}
INLINE(static uint32_t CellToIndex(uint32_t index)) {
return index << kBitsPerCellLog2;
}
INLINE(static uint32_t CellAlignIndex(uint32_t index)) {
return (index + kBitIndexMask) & ~kBitIndexMask;
}
INLINE(MarkBit::CellType* cells()) {
return reinterpret_cast<MarkBit::CellType*>(this);
}
INLINE(Address address()) {
return reinterpret_cast<Address>(this);
}
INLINE(static Bitmap* FromAddress(Address addr)) {
return reinterpret_cast<Bitmap*>(addr);
}
inline MarkBit MarkBitFromIndex(uint32_t index, bool data_only = false) {
MarkBit::CellType mask = 1 << (index & kBitIndexMask);
MarkBit::CellType* cell = this->cells() + (index >> kBitsPerCellLog2);
return MarkBit(cell, mask, data_only);
}
static inline void Clear(MemoryChunk* chunk);
static void PrintWord(uint32_t word, uint32_t himask = 0) {
for (uint32_t mask = 1; mask != 0; mask <<= 1) {
if ((mask & himask) != 0) PrintF("[");
PrintF((mask & word) ? "1" : "0");
if ((mask & himask) != 0) PrintF("]");
}
}
class CellPrinter {
public:
CellPrinter() : seq_start(0), seq_type(0), seq_length(0) { }
void Print(uint32_t pos, uint32_t cell) {
if (cell == seq_type) {
seq_length++;
return;
}
Flush();
if (IsSeq(cell)) {
seq_start = pos;
seq_length = 0;
seq_type = cell;
return;
}
PrintF("%d: ", pos);
PrintWord(cell);
PrintF("\n");
}
void Flush() {
if (seq_length > 0) {
PrintF("%d: %dx%d\n",
seq_start,
seq_type == 0 ? 0 : 1,
seq_length * kBitsPerCell);
seq_length = 0;
}
}
static bool IsSeq(uint32_t cell) { return cell == 0 || cell == 0xFFFFFFFF; }
private:
uint32_t seq_start;
uint32_t seq_type;
uint32_t seq_length;
};
void Print() {
CellPrinter printer;
for (int i = 0; i < CellsCount(); i++) {
printer.Print(i, cells()[i]);
}
printer.Flush();
PrintF("\n");
}
bool IsClean() {
for (int i = 0; i < CellsCount(); i++) {
if (cells()[i] != 0) {
return false;
}
}
return true;
}
};
class SkipList;
class SlotsBuffer;
// MemoryChunk represents a memory region owned by a specific space.
// It is divided into the header and the body. Chunk start is always
// 1MB aligned. Start of the body is aligned so it can accommodate
// any heap object.
class MemoryChunk {
public:
// Only works if the pointer is in the first kPageSize of the MemoryChunk.
static MemoryChunk* FromAddress(Address a) {
return reinterpret_cast<MemoryChunk*>(OffsetFrom(a) & ~kAlignmentMask);
}
// Only works for addresses in pointer spaces, not data or code spaces.
static inline MemoryChunk* FromAnyPointerAddress(Address addr);
Address address() { return reinterpret_cast<Address>(this); }
bool is_valid() { return address() != NULL; }
MemoryChunk* next_chunk() const { return next_chunk_; }
MemoryChunk* prev_chunk() const { return prev_chunk_; }
void set_next_chunk(MemoryChunk* next) { next_chunk_ = next; }
void set_prev_chunk(MemoryChunk* prev) { prev_chunk_ = prev; }
Space* owner() const {
if ((reinterpret_cast<intptr_t>(owner_) & kFailureTagMask) ==
kFailureTag) {
return reinterpret_cast<Space*>(owner_ - kFailureTag);
} else {
return NULL;
}
}
void set_owner(Space* space) {
ASSERT((reinterpret_cast<intptr_t>(space) & kFailureTagMask) == 0);
owner_ = reinterpret_cast<Address>(space) + kFailureTag;
ASSERT((reinterpret_cast<intptr_t>(owner_) & kFailureTagMask) ==
kFailureTag);
}
VirtualMemory* reserved_memory() {
return &reservation_;
}
void InitializeReservedMemory() {
reservation_.Reset();
}
void set_reserved_memory(VirtualMemory* reservation) {
ASSERT_NOT_NULL(reservation);
reservation_.TakeControl(reservation);
}
bool scan_on_scavenge() { return IsFlagSet(SCAN_ON_SCAVENGE); }
void initialize_scan_on_scavenge(bool scan) {
if (scan) {
SetFlag(SCAN_ON_SCAVENGE);
} else {
ClearFlag(SCAN_ON_SCAVENGE);
}
}
inline void set_scan_on_scavenge(bool scan);
int store_buffer_counter() { return store_buffer_counter_; }
void set_store_buffer_counter(int counter) {
store_buffer_counter_ = counter;
}
bool Contains(Address addr) {
return addr >= area_start() && addr < area_end();
}
// Checks whether addr can be a limit of addresses in this page.
// It's a limit if it's in the page, or if it's just after the
// last byte of the page.
bool ContainsLimit(Address addr) {
return addr >= area_start() && addr <= area_end();
}
// Every n write barrier invocations we go to runtime even though
// we could have handled it in generated code. This lets us check
// whether we have hit the limit and should do some more marking.
static const int kWriteBarrierCounterGranularity = 500;
enum MemoryChunkFlags {
IS_EXECUTABLE,
ABOUT_TO_BE_FREED,
POINTERS_TO_HERE_ARE_INTERESTING,
POINTERS_FROM_HERE_ARE_INTERESTING,
SCAN_ON_SCAVENGE,
IN_FROM_SPACE, // Mutually exclusive with IN_TO_SPACE.
IN_TO_SPACE, // All pages in new space has one of these two set.
NEW_SPACE_BELOW_AGE_MARK,
CONTAINS_ONLY_DATA,
EVACUATION_CANDIDATE,
RESCAN_ON_EVACUATION,
// Pages swept precisely can be iterated, hitting only the live objects.
// Whereas those swept conservatively cannot be iterated over. Both flags
// indicate that marking bits have been cleared by the sweeper, otherwise
// marking bits are still intact.
WAS_SWEPT_PRECISELY,
WAS_SWEPT_CONSERVATIVELY,
// Last flag, keep at bottom.
NUM_MEMORY_CHUNK_FLAGS
};
static const int kPointersToHereAreInterestingMask =
1 << POINTERS_TO_HERE_ARE_INTERESTING;
static const int kPointersFromHereAreInterestingMask =
1 << POINTERS_FROM_HERE_ARE_INTERESTING;
static const int kEvacuationCandidateMask =
1 << EVACUATION_CANDIDATE;
static const int kSkipEvacuationSlotsRecordingMask =
(1 << EVACUATION_CANDIDATE) |
(1 << RESCAN_ON_EVACUATION) |
(1 << IN_FROM_SPACE) |
(1 << IN_TO_SPACE);
void SetFlag(int flag) {
flags_ |= static_cast<uintptr_t>(1) << flag;
}
void ClearFlag(int flag) {
flags_ &= ~(static_cast<uintptr_t>(1) << flag);
}
void SetFlagTo(int flag, bool value) {
if (value) {
SetFlag(flag);
} else {
ClearFlag(flag);
}
}
bool IsFlagSet(int flag) {
return (flags_ & (static_cast<uintptr_t>(1) << flag)) != 0;
}
// Set or clear multiple flags at a time. The flags in the mask
// are set to the value in "flags", the rest retain the current value
// in flags_.
void SetFlags(intptr_t flags, intptr_t mask) {
flags_ = (flags_ & ~mask) | (flags & mask);
}
// Return all current flags.
intptr_t GetFlags() { return flags_; }
// Manage live byte count (count of bytes known to be live,
// because they are marked black).
void ResetLiveBytes() {
if (FLAG_gc_verbose) {
PrintF("ResetLiveBytes:%p:%x->0\n",
static_cast<void*>(this), live_byte_count_);
}
live_byte_count_ = 0;
}
void IncrementLiveBytes(int by) {
if (FLAG_gc_verbose) {
printf("UpdateLiveBytes:%p:%x%c=%x->%x\n",
static_cast<void*>(this), live_byte_count_,
((by < 0) ? '-' : '+'), ((by < 0) ? -by : by),
live_byte_count_ + by);
}
live_byte_count_ += by;
ASSERT_LE(static_cast<unsigned>(live_byte_count_), size_);
}
int LiveBytes() {
ASSERT(static_cast<unsigned>(live_byte_count_) <= size_);
return live_byte_count_;
}
int write_barrier_counter() {
return static_cast<int>(write_barrier_counter_);
}
void set_write_barrier_counter(int counter) {
write_barrier_counter_ = counter;
}
static void IncrementLiveBytesFromGC(Address address, int by) {
MemoryChunk::FromAddress(address)->IncrementLiveBytes(by);
}
static void IncrementLiveBytesFromMutator(Address address, int by);
static const intptr_t kAlignment =
(static_cast<uintptr_t>(1) << kPageSizeBits);
static const intptr_t kAlignmentMask = kAlignment - 1;
static const intptr_t kSizeOffset = kPointerSize + kPointerSize;
static const intptr_t kLiveBytesOffset =
kSizeOffset + kPointerSize + kPointerSize + kPointerSize +
kPointerSize + kPointerSize +
kPointerSize + kPointerSize + kPointerSize + kIntSize;
static const size_t kSlotsBufferOffset = kLiveBytesOffset + kIntSize;
static const size_t kWriteBarrierCounterOffset =
kSlotsBufferOffset + kPointerSize + kPointerSize;
static const size_t kHeaderSize = kWriteBarrierCounterOffset + kPointerSize;
static const int kBodyOffset =
CODE_POINTER_ALIGN(kHeaderSize + Bitmap::kSize);
// The start offset of the object area in a page. Aligned to both maps and
// code alignment to be suitable for both. Also aligned to 32 words because
// the marking bitmap is arranged in 32 bit chunks.
static const int kObjectStartAlignment = 32 * kPointerSize;
static const int kObjectStartOffset = kBodyOffset - 1 +
(kObjectStartAlignment - (kBodyOffset - 1) % kObjectStartAlignment);
size_t size() const { return size_; }
void set_size(size_t size) {
size_ = size;
}
void SetArea(Address area_start, Address area_end) {
area_start_ = area_start;
area_end_ = area_end;
}
Executability executable() {
return IsFlagSet(IS_EXECUTABLE) ? EXECUTABLE : NOT_EXECUTABLE;
}
bool ContainsOnlyData() {
return IsFlagSet(CONTAINS_ONLY_DATA);
}
bool InNewSpace() {
return (flags_ & ((1 << IN_FROM_SPACE) | (1 << IN_TO_SPACE))) != 0;
}
bool InToSpace() {
return IsFlagSet(IN_TO_SPACE);
}
bool InFromSpace() {
return IsFlagSet(IN_FROM_SPACE);
}
// ---------------------------------------------------------------------
// Markbits support
inline Bitmap* markbits() {
return Bitmap::FromAddress(address() + kHeaderSize);
}
void PrintMarkbits() { markbits()->Print(); }
inline uint32_t AddressToMarkbitIndex(Address addr) {
return static_cast<uint32_t>(addr - this->address()) >> kPointerSizeLog2;
}
inline static uint32_t FastAddressToMarkbitIndex(Address addr) {
const intptr_t offset =
reinterpret_cast<intptr_t>(addr) & kAlignmentMask;
return static_cast<uint32_t>(offset) >> kPointerSizeLog2;
}
inline Address MarkbitIndexToAddress(uint32_t index) {
return this->address() + (index << kPointerSizeLog2);
}
void InsertAfter(MemoryChunk* other);
void Unlink();
inline Heap* heap() { return heap_; }
static const int kFlagsOffset = kPointerSize * 3;
bool IsEvacuationCandidate() { return IsFlagSet(EVACUATION_CANDIDATE); }
bool ShouldSkipEvacuationSlotRecording() {
return (flags_ & kSkipEvacuationSlotsRecordingMask) != 0;
}
inline SkipList* skip_list() {
return skip_list_;
}
inline void set_skip_list(SkipList* skip_list) {
skip_list_ = skip_list;
}
inline SlotsBuffer* slots_buffer() {
return slots_buffer_;
}
inline SlotsBuffer** slots_buffer_address() {
return &slots_buffer_;
}
void MarkEvacuationCandidate() {
ASSERT(slots_buffer_ == NULL);
SetFlag(EVACUATION_CANDIDATE);
}
void ClearEvacuationCandidate() {
ASSERT(slots_buffer_ == NULL);
ClearFlag(EVACUATION_CANDIDATE);
}
Address area_start() { return area_start_; }
Address area_end() { return area_end_; }
int area_size() {
return static_cast<int>(area_end() - area_start());
}
protected:
MemoryChunk* next_chunk_;
MemoryChunk* prev_chunk_;
size_t size_;
intptr_t flags_;
// Start and end of allocatable memory on this chunk.
Address area_start_;
Address area_end_;
// If the chunk needs to remember its memory reservation, it is stored here.
VirtualMemory reservation_;
// The identity of the owning space. This is tagged as a failure pointer, but
// no failure can be in an object, so this can be distinguished from any entry
// in a fixed array.
Address owner_;
Heap* heap_;
// Used by the store buffer to keep track of which pages to mark scan-on-
// scavenge.
int store_buffer_counter_;
// Count of bytes marked black on page.
int live_byte_count_;
SlotsBuffer* slots_buffer_;
SkipList* skip_list_;
intptr_t write_barrier_counter_;
static MemoryChunk* Initialize(Heap* heap,
Address base,
size_t size,
Address area_start,
Address area_end,
Executability executable,
Space* owner);
friend class MemoryAllocator;
};
STATIC_CHECK(sizeof(MemoryChunk) <= MemoryChunk::kHeaderSize);
// -----------------------------------------------------------------------------
// A page is a memory chunk of a size 1MB. Large object pages may be larger.
//
// The only way to get a page pointer is by calling factory methods:
// Page* p = Page::FromAddress(addr); or
// Page* p = Page::FromAllocationTop(top);
class Page : public MemoryChunk {
public:
// Returns the page containing a given address. The address ranges
// from [page_addr .. page_addr + kPageSize[
// This only works if the object is in fact in a page. See also MemoryChunk::
// FromAddress() and FromAnyAddress().
INLINE(static Page* FromAddress(Address a)) {
return reinterpret_cast<Page*>(OffsetFrom(a) & ~kPageAlignmentMask);
}
// Returns the page containing an allocation top. Because an allocation
// top address can be the upper bound of the page, we need to subtract
// it with kPointerSize first. The address ranges from
// [page_addr + kObjectStartOffset .. page_addr + kPageSize].
INLINE(static Page* FromAllocationTop(Address top)) {
Page* p = FromAddress(top - kPointerSize);
return p;
}
// Returns the next page in the chain of pages owned by a space.
inline Page* next_page();
inline Page* prev_page();
inline void set_next_page(Page* page);
inline void set_prev_page(Page* page);
// Checks whether an address is page aligned.
static bool IsAlignedToPageSize(Address a) {
return 0 == (OffsetFrom(a) & kPageAlignmentMask);
}
// Returns the offset of a given address to this page.
INLINE(int Offset(Address a)) {
int offset = static_cast<int>(a - address());
return offset;
}
// Returns the address for a given offset to the this page.
Address OffsetToAddress(int offset) {
ASSERT_PAGE_OFFSET(offset);
return address() + offset;
}
// ---------------------------------------------------------------------
// Page size in bytes. This must be a multiple of the OS page size.
static const int kPageSize = 1 << kPageSizeBits;
// Object area size in bytes.
static const int kNonCodeObjectAreaSize = kPageSize - kObjectStartOffset;
// Maximum object size that fits in a page.
static const int kMaxNonCodeHeapObjectSize = kNonCodeObjectAreaSize;
// Page size mask.
static const intptr_t kPageAlignmentMask = (1 << kPageSizeBits) - 1;
inline void ClearGCFields();
static inline Page* Initialize(Heap* heap,
MemoryChunk* chunk,
Executability executable,
PagedSpace* owner);
void InitializeAsAnchor(PagedSpace* owner);
bool WasSweptPrecisely() { return IsFlagSet(WAS_SWEPT_PRECISELY); }
bool WasSweptConservatively() { return IsFlagSet(WAS_SWEPT_CONSERVATIVELY); }
bool WasSwept() { return WasSweptPrecisely() || WasSweptConservatively(); }
void MarkSweptPrecisely() { SetFlag(WAS_SWEPT_PRECISELY); }
void MarkSweptConservatively() { SetFlag(WAS_SWEPT_CONSERVATIVELY); }
void ClearSweptPrecisely() { ClearFlag(WAS_SWEPT_PRECISELY); }
void ClearSweptConservatively() { ClearFlag(WAS_SWEPT_CONSERVATIVELY); }
#ifdef DEBUG
void Print();
#endif // DEBUG
friend class MemoryAllocator;
};
STATIC_CHECK(sizeof(Page) <= MemoryChunk::kHeaderSize);
class LargePage : public MemoryChunk {
public:
HeapObject* GetObject() {
return HeapObject::FromAddress(area_start());
}
inline LargePage* next_page() const {
return static_cast<LargePage*>(next_chunk());
}
inline void set_next_page(LargePage* page) {
set_next_chunk(page);
}
private:
static inline LargePage* Initialize(Heap* heap, MemoryChunk* chunk);
friend class MemoryAllocator;
};
STATIC_CHECK(sizeof(LargePage) <= MemoryChunk::kHeaderSize);
// ----------------------------------------------------------------------------
// Space is the abstract superclass for all allocation spaces.
class Space : public Malloced {
public:
Space(Heap* heap, AllocationSpace id, Executability executable)
: heap_(heap), id_(id), executable_(executable) {}
virtual ~Space() {}
Heap* heap() const { return heap_; }
// Does the space need executable memory?
Executability executable() { return executable_; }
// Identity used in error reporting.
AllocationSpace identity() { return id_; }
// Returns allocated size.
virtual intptr_t Size() = 0;
// Returns size of objects. Can differ from the allocated size
// (e.g. see LargeObjectSpace).
virtual intptr_t SizeOfObjects() { return Size(); }
virtual int RoundSizeDownToObjectAlignment(int size) {
if (id_ == CODE_SPACE) {
return RoundDown(size, kCodeAlignment);
} else {
return RoundDown(size, kPointerSize);
}
}
#ifdef DEBUG
virtual void Print() = 0;
#endif
private:
Heap* heap_;
AllocationSpace id_;
Executability executable_;
};
// ----------------------------------------------------------------------------
// All heap objects containing executable code (code objects) must be allocated
// from a 2 GB range of memory, so that they can call each other using 32-bit
// displacements. This happens automatically on 32-bit platforms, where 32-bit
// displacements cover the entire 4GB virtual address space. On 64-bit
// platforms, we support this using the CodeRange object, which reserves and
// manages a range of virtual memory.
class CodeRange {
public:
explicit CodeRange(Isolate* isolate);
~CodeRange() { TearDown(); }
// Reserves a range of virtual memory, but does not commit any of it.
// Can only be called once, at heap initialization time.
// Returns false on failure.
bool SetUp(const size_t requested_size);
// Frees the range of virtual memory, and frees the data structures used to
// manage it.
void TearDown();
bool valid() { return code_range_ != NULL; }
Address start() {
ASSERT(valid());
return static_cast<Address>(code_range_->address());
}
bool contains(Address address) {
if (!valid()) return false;
Address start = static_cast<Address>(code_range_->address());
return start <= address && address < start + code_range_->size();
}
// Allocates a chunk of memory from the large-object portion of
// the code range. On platforms with no separate code range, should
// not be called.
MUST_USE_RESULT Address AllocateRawMemory(const size_t requested,
size_t* allocated);
void FreeRawMemory(Address buf, size_t length);
private:
Isolate* isolate_;
// The reserved range of virtual memory that all code objects are put in.
VirtualMemory* code_range_;
// Plain old data class, just a struct plus a constructor.
class FreeBlock {
public:
FreeBlock(Address start_arg, size_t size_arg)
: start(start_arg), size(size_arg) {
ASSERT(IsAddressAligned(start, MemoryChunk::kAlignment));
ASSERT(size >= static_cast<size_t>(Page::kPageSize));
}
FreeBlock(void* start_arg, size_t size_arg)
: start(static_cast<Address>(start_arg)), size(size_arg) {
ASSERT(IsAddressAligned(start, MemoryChunk::kAlignment));
ASSERT(size >= static_cast<size_t>(Page::kPageSize));
}
Address start;
size_t size;
};
// Freed blocks of memory are added to the free list. When the allocation
// list is exhausted, the free list is sorted and merged to make the new
// allocation list.
List<FreeBlock> free_list_;
// Memory is allocated from the free blocks on the allocation list.
// The block at current_allocation_block_index_ is the current block.
List<FreeBlock> allocation_list_;
int current_allocation_block_index_;
// Finds a block on the allocation list that contains at least the
// requested amount of memory. If none is found, sorts and merges
// the existing free memory blocks, and searches again.
// If none can be found, terminates V8 with FatalProcessOutOfMemory.
void GetNextAllocationBlock(size_t requested);
// Compares the start addresses of two free blocks.
static int CompareFreeBlockAddress(const FreeBlock* left,
const FreeBlock* right);
DISALLOW_COPY_AND_ASSIGN(CodeRange);
};
class SkipList {
public:
SkipList() {
Clear();
}
void Clear() {
for (int idx = 0; idx < kSize; idx++) {
starts_[idx] = reinterpret_cast<Address>(-1);
}
}
Address StartFor(Address addr) {
return starts_[RegionNumber(addr)];
}
void AddObject(Address addr, int size) {
int start_region = RegionNumber(addr);
int end_region = RegionNumber(addr + size - kPointerSize);
for (int idx = start_region; idx <= end_region; idx++) {
if (starts_[idx] > addr) starts_[idx] = addr;
}
}
static inline int RegionNumber(Address addr) {
return (OffsetFrom(addr) & Page::kPageAlignmentMask) >> kRegionSizeLog2;
}
static void Update(Address addr, int size) {
Page* page = Page::FromAddress(addr);
SkipList* list = page->skip_list();
if (list == NULL) {
list = new SkipList();
page->set_skip_list(list);
}
list->AddObject(addr, size);
}
private:
static const int kRegionSizeLog2 = 13;
static const int kRegionSize = 1 << kRegionSizeLog2;
static const int kSize = Page::kPageSize / kRegionSize;
STATIC_ASSERT(Page::kPageSize % kRegionSize == 0);
Address starts_[kSize];
};
// ----------------------------------------------------------------------------
// A space acquires chunks of memory from the operating system. The memory
// allocator allocated and deallocates pages for the paged heap spaces and large
// pages for large object space.
//
// Each space has to manage it's own pages.
//
class MemoryAllocator {
public:
explicit MemoryAllocator(Isolate* isolate);
// Initializes its internal bookkeeping structures.
// Max capacity of the total space and executable memory limit.
bool SetUp(intptr_t max_capacity, intptr_t capacity_executable);
void TearDown();
Page* AllocatePage(
intptr_t size, PagedSpace* owner, Executability executable);
LargePage* AllocateLargePage(
intptr_t object_size, Space* owner, Executability executable);
void Free(MemoryChunk* chunk);
// Returns the maximum available bytes of heaps.
intptr_t Available() { return capacity_ < size_ ? 0 : capacity_ - size_; }
// Returns allocated spaces in bytes.
intptr_t Size() { return size_; }
// Returns the maximum available executable bytes of heaps.
intptr_t AvailableExecutable() {
if (capacity_executable_ < size_executable_) return 0;
return capacity_executable_ - size_executable_;
}
// Returns allocated executable spaces in bytes.
intptr_t SizeExecutable() { return size_executable_; }
// Returns maximum available bytes that the old space can have.
intptr_t MaxAvailable() {
return (Available() / Page::kPageSize) * Page::kMaxNonCodeHeapObjectSize;
}
#ifdef DEBUG
// Reports statistic info of the space.
void ReportStatistics();
#endif
MemoryChunk* AllocateChunk(intptr_t body_size,
Executability executable,
Space* space);
Address ReserveAlignedMemory(size_t requested,
size_t alignment,
VirtualMemory* controller);
Address AllocateAlignedMemory(size_t requested,
size_t alignment,
Executability executable,
VirtualMemory* controller);
void FreeMemory(VirtualMemory* reservation, Executability executable);
void FreeMemory(Address addr, size_t size, Executability executable);
// Commit a contiguous block of memory from the initial chunk. Assumes that
// the address is not NULL, the size is greater than zero, and that the
// block is contained in the initial chunk. Returns true if it succeeded
// and false otherwise.
bool CommitBlock(Address start, size_t size, Executability executable);
// Uncommit a contiguous block of memory [start..(start+size)[.
// start is not NULL, the size is greater than zero, and the
// block is contained in the initial chunk. Returns true if it succeeded
// and false otherwise.
bool UncommitBlock(Address start, size_t size);
// Zaps a contiguous block of memory [start..(start+size)[ thus
// filling it up with a recognizable non-NULL bit pattern.
void ZapBlock(Address start, size_t size);
void PerformAllocationCallback(ObjectSpace space,
AllocationAction action,
size_t size);
void AddMemoryAllocationCallback(MemoryAllocationCallback callback,
ObjectSpace space,
AllocationAction action);
void RemoveMemoryAllocationCallback(
MemoryAllocationCallback callback);
bool MemoryAllocationCallbackRegistered(
MemoryAllocationCallback callback);
static int CodePageGuardStartOffset();
static int CodePageGuardSize();
static int CodePageAreaStartOffset();
static int CodePageAreaEndOffset();
static int CodePageAreaSize() {
return CodePageAreaEndOffset() - CodePageAreaStartOffset();
}
MUST_USE_RESULT static bool CommitCodePage(VirtualMemory* vm,
Address start,
size_t size);
private:
Isolate* isolate_;
// Maximum space size in bytes.
size_t capacity_;
// Maximum subset of capacity_ that can be executable
size_t capacity_executable_;
// Allocated space size in bytes.
size_t size_;
// Allocated executable space size in bytes.
size_t size_executable_;
struct MemoryAllocationCallbackRegistration {
MemoryAllocationCallbackRegistration(MemoryAllocationCallback callback,
ObjectSpace space,
AllocationAction action)
: callback(callback), space(space), action(action) {
}
MemoryAllocationCallback callback;
ObjectSpace space;
AllocationAction action;
};
// A List of callback that are triggered when memory is allocated or free'd
List<MemoryAllocationCallbackRegistration>
memory_allocation_callbacks_;
// Initializes pages in a chunk. Returns the first page address.
// This function and GetChunkId() are provided for the mark-compact
// collector to rebuild page headers in the from space, which is
// used as a marking stack and its page headers are destroyed.
Page* InitializePagesInChunk(int chunk_id, int pages_in_chunk,
PagedSpace* owner);
DISALLOW_IMPLICIT_CONSTRUCTORS(MemoryAllocator);
};
// -----------------------------------------------------------------------------
// Interface for heap object iterator to be implemented by all object space
// object iterators.
//
// NOTE: The space specific object iterators also implements the own next()
// method which is used to avoid using virtual functions
// iterating a specific space.
class ObjectIterator : public Malloced {
public:
virtual ~ObjectIterator() { }
virtual HeapObject* next_object() = 0;
};
// -----------------------------------------------------------------------------
// Heap object iterator in new/old/map spaces.
//
// A HeapObjectIterator iterates objects from the bottom of the given space
// to its top or from the bottom of the given page to its top.
//
// If objects are allocated in the page during iteration the iterator may
// or may not iterate over those objects. The caller must create a new
// iterator in order to be sure to visit these new objects.
class HeapObjectIterator: public ObjectIterator {
public:
// Creates a new object iterator in a given space.
// If the size function is not given, the iterator calls the default
// Object::Size().
explicit HeapObjectIterator(PagedSpace* space);
HeapObjectIterator(PagedSpace* space, HeapObjectCallback size_func);
HeapObjectIterator(Page* page, HeapObjectCallback size_func);
// Advance to the next object, skipping free spaces and other fillers and
// skipping the special garbage section of which there is one per space.
// Returns NULL when the iteration has ended.
inline HeapObject* Next() {
do {
HeapObject* next_obj = FromCurrentPage();
if (next_obj != NULL) return next_obj;
} while (AdvanceToNextPage());
return NULL;
}
virtual HeapObject* next_object() {
return Next();
}
private:
enum PageMode { kOnePageOnly, kAllPagesInSpace };
Address cur_addr_; // Current iteration point.
Address cur_end_; // End iteration point.
HeapObjectCallback size_func_; // Size function or NULL.
PagedSpace* space_;
PageMode page_mode_;
// Fast (inlined) path of next().
inline HeapObject* FromCurrentPage();
// Slow path of next(), goes into the next page. Returns false if the
// iteration has ended.
bool AdvanceToNextPage();
// Initializes fields.
inline void Initialize(PagedSpace* owner,
Address start,
Address end,
PageMode mode,
HeapObjectCallback size_func);
};
// -----------------------------------------------------------------------------
// A PageIterator iterates the pages in a paged space.
class PageIterator BASE_EMBEDDED {
public:
explicit inline PageIterator(PagedSpace* space);
inline bool has_next();
inline Page* next();
private:
PagedSpace* space_;
Page* prev_page_; // Previous page returned.
// Next page that will be returned. Cached here so that we can use this
// iterator for operations that deallocate pages.
Page* next_page_;
};
// -----------------------------------------------------------------------------
// A space has a circular list of pages. The next page can be accessed via
// Page::next_page() call.
// An abstraction of allocation and relocation pointers in a page-structured
// space.
class AllocationInfo {
public:
AllocationInfo() : top(NULL), limit(NULL) {
}
Address top; // Current allocation top.
Address limit; // Current allocation limit.
#ifdef DEBUG
bool VerifyPagedAllocation() {
return (Page::FromAllocationTop(top) == Page::FromAllocationTop(limit))
&& (top <= limit);
}
#endif
};
// An abstraction of the accounting statistics of a page-structured space.
// The 'capacity' of a space is the number of object-area bytes (i.e., not
// including page bookkeeping structures) currently in the space. The 'size'
// of a space is the number of allocated bytes, the 'waste' in the space is
// the number of bytes that are not allocated and not available to
// allocation without reorganizing the space via a GC (e.g. small blocks due
// to internal fragmentation, top of page areas in map space), and the bytes
// 'available' is the number of unallocated bytes that are not waste. The
// capacity is the sum of size, waste, and available.
//
// The stats are only set by functions that ensure they stay balanced. These
// functions increase or decrease one of the non-capacity stats in
// conjunction with capacity, or else they always balance increases and
// decreases to the non-capacity stats.
class AllocationStats BASE_EMBEDDED {
public:
AllocationStats() { Clear(); }
// Zero out all the allocation statistics (i.e., no capacity).
void Clear() {
capacity_ = 0;
size_ = 0;
waste_ = 0;
}
void ClearSizeWaste() {
size_ = capacity_;
waste_ = 0;
}
// Reset the allocation statistics (i.e., available = capacity with no
// wasted or allocated bytes).
void Reset() {
size_ = 0;
waste_ = 0;
}
// Accessors for the allocation statistics.
intptr_t Capacity() { return capacity_; }
intptr_t Size() { return size_; }
intptr_t Waste() { return waste_; }
// Grow the space by adding available bytes. They are initially marked as
// being in use (part of the size), but will normally be immediately freed,
// putting them on the free list and removing them from size_.
void ExpandSpace(int size_in_bytes) {
capacity_ += size_in_bytes;
size_ += size_in_bytes;
ASSERT(size_ >= 0);
}
// Shrink the space by removing available bytes. Since shrinking is done
// during sweeping, bytes have been marked as being in use (part of the size)
// and are hereby freed.
void ShrinkSpace(int size_in_bytes) {
capacity_ -= size_in_bytes;
size_ -= size_in_bytes;
ASSERT(size_ >= 0);
}
// Allocate from available bytes (available -> size).
void AllocateBytes(intptr_t size_in_bytes) {
size_ += size_in_bytes;
ASSERT(size_ >= 0);
}
// Free allocated bytes, making them available (size -> available).
void DeallocateBytes(intptr_t size_in_bytes) {
size_ -= size_in_bytes;
ASSERT(size_ >= 0);
}
// Waste free bytes (available -> waste).
void WasteBytes(int size_in_bytes) {
size_ -= size_in_bytes;
waste_ += size_in_bytes;
ASSERT(size_ >= 0);
}
private:
intptr_t capacity_;
intptr_t size_;
intptr_t waste_;
};
// -----------------------------------------------------------------------------
// Free lists for old object spaces
//
// Free-list nodes are free blocks in the heap. They look like heap objects
// (free-list node pointers have the heap object tag, and they have a map like
// a heap object). They have a size and a next pointer. The next pointer is
// the raw address of the next free list node (or NULL).
class FreeListNode: public HeapObject {
public:
// Obtain a free-list node from a raw address. This is not a cast because
// it does not check nor require that the first word at the address is a map
// pointer.
static FreeListNode* FromAddress(Address address) {
return reinterpret_cast<FreeListNode*>(HeapObject::FromAddress(address));
}
static inline bool IsFreeListNode(HeapObject* object);
// Set the size in bytes, which can be read with HeapObject::Size(). This
// function also writes a map to the first word of the block so that it
// looks like a heap object to the garbage collector and heap iteration
// functions.
void set_size(Heap* heap, int size_in_bytes);
// Accessors for the next field.
inline FreeListNode* next();
inline FreeListNode** next_address();
inline void set_next(FreeListNode* next);
inline void Zap();
static inline FreeListNode* cast(MaybeObject* maybe) {
ASSERT(!maybe->IsFailure());
return reinterpret_cast<FreeListNode*>(maybe);
}
private:
static const int kNextOffset = POINTER_SIZE_ALIGN(FreeSpace::kHeaderSize);
DISALLOW_IMPLICIT_CONSTRUCTORS(FreeListNode);
};
// The free list for the old space. The free list is organized in such a way
// as to encourage objects allocated around the same time to be near each
// other. The normal way to allocate is intended to be by bumping a 'top'
// pointer until it hits a 'limit' pointer. When the limit is hit we need to
// find a new space to allocate from. This is done with the free list, which
// is divided up into rough categories to cut down on waste. Having finer
// categories would scatter allocation more.
// The old space free list is organized in categories.
// 1-31 words: Such small free areas are discarded for efficiency reasons.
// They can be reclaimed by the compactor. However the distance between top
// and limit may be this small.
// 32-255 words: There is a list of spaces this large. It is used for top and
// limit when the object we need to allocate is 1-31 words in size. These
// spaces are called small.
// 256-2047 words: There is a list of spaces this large. It is used for top and
// limit when the object we need to allocate is 32-255 words in size. These
// spaces are called medium.
// 1048-16383 words: There is a list of spaces this large. It is used for top
// and limit when the object we need to allocate is 256-2047 words in size.
// These spaces are call large.
// At least 16384 words. This list is for objects of 2048 words or larger.
// Empty pages are added to this list. These spaces are called huge.
class FreeList BASE_EMBEDDED {
public:
explicit FreeList(PagedSpace* owner);
// Clear the free list.
void Reset();
// Return the number of bytes available on the free list.
intptr_t available() { return available_; }
// Place a node on the free list. The block of size 'size_in_bytes'
// starting at 'start' is placed on the free list. The return value is the
// number of bytes that have been lost due to internal fragmentation by
// freeing the block. Bookkeeping information will be written to the block,
// i.e., its contents will be destroyed. The start address should be word
// aligned, and the size should be a non-zero multiple of the word size.
int Free(Address start, int size_in_bytes);
// Allocate a block of size 'size_in_bytes' from the free list. The block
// is unitialized. A failure is returned if no block is available. The
// number of bytes lost to fragmentation is returned in the output parameter
// 'wasted_bytes'. The size should be a non-zero multiple of the word size.
MUST_USE_RESULT HeapObject* Allocate(int size_in_bytes);
#ifdef DEBUG
void Zap();
static intptr_t SumFreeList(FreeListNode* node);
static int FreeListLength(FreeListNode* cur);
intptr_t SumFreeLists();
bool IsVeryLong();
#endif
// Used after booting the VM.
void RepairLists(Heap* heap);
struct SizeStats {
intptr_t Total() {
return small_size_ + medium_size_ + large_size_ + huge_size_;
}
intptr_t small_size_;
intptr_t medium_size_;
intptr_t large_size_;
intptr_t huge_size_;
};
void CountFreeListItems(Page* p, SizeStats* sizes);
intptr_t EvictFreeListItems(Page* p);
private:
// The size range of blocks, in bytes.
static const int kMinBlockSize = 3 * kPointerSize;
static const int kMaxBlockSize = Page::kMaxNonCodeHeapObjectSize;
FreeListNode* PickNodeFromList(FreeListNode** list, int* node_size);
FreeListNode* FindNodeFor(int size_in_bytes, int* node_size);
PagedSpace* owner_;
Heap* heap_;
// Total available bytes in all blocks on this free list.
int available_;
static const int kSmallListMin = 0x20 * kPointerSize;
static const int kSmallListMax = 0xff * kPointerSize;
static const int kMediumListMax = 0x7ff * kPointerSize;
static const int kLargeListMax = 0x3fff * kPointerSize;
static const int kSmallAllocationMax = kSmallListMin - kPointerSize;
static const int kMediumAllocationMax = kSmallListMax;
static const int kLargeAllocationMax = kMediumListMax;
FreeListNode* small_list_;
FreeListNode* medium_list_;
FreeListNode* large_list_;
FreeListNode* huge_list_;
DISALLOW_IMPLICIT_CONSTRUCTORS(FreeList);
};
class PagedSpace : public Space {
public:
// Creates a space with a maximum capacity, and an id.
PagedSpace(Heap* heap,
intptr_t max_capacity,
AllocationSpace id,
Executability executable);
virtual ~PagedSpace() {}
// Set up the space using the given address range of virtual memory (from
// the memory allocator's initial chunk) if possible. If the block of
// addresses is not big enough to contain a single page-aligned page, a
// fresh chunk will be allocated.
bool SetUp();
// Returns true if the space has been successfully set up and not
// subsequently torn down.
bool HasBeenSetUp();
// Cleans up the space, frees all pages in this space except those belonging
// to the initial chunk, uncommits addresses in the initial chunk.
void TearDown();
// Checks whether an object/address is in this space.
inline bool Contains(Address a);
bool Contains(HeapObject* o) { return Contains(o->address()); }
// Given an address occupied by a live object, return that object if it is
// in this space, or Failure::Exception() if it is not. The implementation
// iterates over objects in the page containing the address, the cost is
// linear in the number of objects in the page. It may be slow.
MUST_USE_RESULT MaybeObject* FindObject(Address addr);
// During boot the free_space_map is created, and afterwards we may need
// to write it into the free list nodes that were already created.
virtual void RepairFreeListsAfterBoot();
// Prepares for a mark-compact GC.
virtual void PrepareForMarkCompact();
// Current capacity without growing (Size() + Available()).
intptr_t Capacity() { return accounting_stats_.Capacity(); }
// Total amount of memory committed for this space. For paged
// spaces this equals the capacity.
intptr_t CommittedMemory() { return Capacity(); }
// Sets the capacity, the available space and the wasted space to zero.
// The stats are rebuilt during sweeping by adding each page to the
// capacity and the size when it is encountered. As free spaces are
// discovered during the sweeping they are subtracted from the size and added
// to the available and wasted totals.
void ClearStats() {
accounting_stats_.ClearSizeWaste();
}
// Available bytes without growing. These are the bytes on the free list.
// The bytes in the linear allocation area are not included in this total
// because updating the stats would slow down allocation. New pages are
// immediately added to the free list so they show up here.
intptr_t Available() { return free_list_.available(); }
// Allocated bytes in this space. Garbage bytes that were not found due to
// lazy sweeping are counted as being allocated! The bytes in the current
// linear allocation area (between top and limit) are also counted here.
virtual intptr_t Size() { return accounting_stats_.Size(); }
// As size, but the bytes in lazily swept pages are estimated and the bytes
// in the current linear allocation area are not included.
virtual intptr_t SizeOfObjects() {
ASSERT(!IsSweepingComplete() || (unswept_free_bytes_ == 0));
return Size() - unswept_free_bytes_ - (limit() - top());
}
// Wasted bytes in this space. These are just the bytes that were thrown away
// due to being too small to use for allocation. They do not include the
// free bytes that were not found at all due to lazy sweeping.
virtual intptr_t Waste() { return accounting_stats_.Waste(); }
// Returns the allocation pointer in this space.
Address top() { return allocation_info_.top; }
Address limit() { return allocation_info_.limit; }
// Allocate the requested number of bytes in the space if possible, return a
// failure object if not.
MUST_USE_RESULT inline MaybeObject* AllocateRaw(int size_in_bytes);
virtual bool ReserveSpace(int bytes);
// Give a block of memory to the space's free list. It might be added to
// the free list or accounted as waste.
// If add_to_freelist is false then just accounting stats are updated and
// no attempt to add area to free list is made.
int Free(Address start, int size_in_bytes) {
int wasted = free_list_.Free(start, size_in_bytes);
accounting_stats_.DeallocateBytes(size_in_bytes - wasted);
return size_in_bytes - wasted;
}
void ResetFreeList() {
free_list_.Reset();
}
// Set space allocation info.
void SetTop(Address top, Address limit) {
ASSERT(top == limit ||
Page::FromAddress(top) == Page::FromAddress(limit - 1));
allocation_info_.top = top;
allocation_info_.limit = limit;
}
void Allocate(int bytes) {
accounting_stats_.AllocateBytes(bytes);
}
void IncreaseCapacity(int size) {
accounting_stats_.ExpandSpace(size);
}
// Releases an unused page and shrinks the space.
void ReleasePage(Page* page);
// Releases all of the unused pages.
void ReleaseAllUnusedPages();
// The dummy page that anchors the linked list of pages.
Page* anchor() { return &anchor_; }
#ifdef VERIFY_HEAP
// Verify integrity of this space.
virtual void Verify(ObjectVisitor* visitor);
// Overridden by subclasses to verify space-specific object
// properties (e.g., only maps or free-list nodes are in map space).
virtual void VerifyObject(HeapObject* obj) {}
#endif
#ifdef DEBUG
// Print meta info and objects in this space.
virtual void Print();
// Reports statistics for the space
void ReportStatistics();
// Report code object related statistics
void CollectCodeStatistics();
static void ReportCodeStatistics();
static void ResetCodeStatistics();
#endif
bool was_swept_conservatively() { return was_swept_conservatively_; }
void set_was_swept_conservatively(bool b) { was_swept_conservatively_ = b; }
// Evacuation candidates are swept by evacuator. Needs to return a valid
// result before _and_ after evacuation has finished.
static bool ShouldBeSweptLazily(Page* p) {
return !p->IsEvacuationCandidate() &&
!p->IsFlagSet(Page::RESCAN_ON_EVACUATION) &&
!p->WasSweptPrecisely();
}
void SetPagesToSweep(Page* first) {
ASSERT(unswept_free_bytes_ == 0);
if (first == &anchor_) first = NULL;
first_unswept_page_ = first;
}
void IncrementUnsweptFreeBytes(int by) {
unswept_free_bytes_ += by;
}
void IncreaseUnsweptFreeBytes(Page* p) {
ASSERT(ShouldBeSweptLazily(p));
unswept_free_bytes_ += (p->area_size() - p->LiveBytes());
}
void DecreaseUnsweptFreeBytes(Page* p) {
ASSERT(ShouldBeSweptLazily(p));
unswept_free_bytes_ -= (p->area_size() - p->LiveBytes());
}
bool AdvanceSweeper(intptr_t bytes_to_sweep);
bool IsSweepingComplete() {
return !first_unswept_page_->is_valid();
}
Page* FirstPage() { return anchor_.next_page(); }
Page* LastPage() { return anchor_.prev_page(); }
void CountFreeListItems(Page* p, FreeList::SizeStats* sizes) {
free_list_.CountFreeListItems(p, sizes);
}
void EvictEvacuationCandidatesFromFreeLists();
bool CanExpand();
// Returns the number of total pages in this space.
int CountTotalPages();
// Return size of allocatable area on a page in this space.
inline int AreaSize() {
return area_size_;
}
protected:
int area_size_;
// Maximum capacity of this space.
intptr_t max_capacity_;
intptr_t SizeOfFirstPage();
// Accounting information for this space.
AllocationStats accounting_stats_;
// The dummy page that anchors the double linked list of pages.
Page anchor_;
// The space's free list.
FreeList free_list_;
// Normal allocation information.
AllocationInfo allocation_info_;
// Bytes of each page that cannot be allocated. Possibly non-zero
// for pages in spaces with only fixed-size objects. Always zero
// for pages in spaces with variable sized objects (those pages are
// padded with free-list nodes).
int page_extra_;
bool was_swept_conservatively_;
// The first page to be swept when the lazy sweeper advances. Is set
// to NULL when all pages have been swept.
Page* first_unswept_page_;
// The number of free bytes which could be reclaimed by advancing the
// lazy sweeper. This is only an estimation because lazy sweeping is
// done conservatively.
intptr_t unswept_free_bytes_;
// Expands the space by allocating a fixed number of pages. Returns false if
// it cannot allocate requested number of pages from OS, or if the hard heap
// size limit has been hit.
bool Expand();
// Generic fast case allocation function that tries linear allocation at the
// address denoted by top in allocation_info_.
inline HeapObject* AllocateLinearly(int size_in_bytes);
// Slow path of AllocateRaw. This function is space-dependent.
MUST_USE_RESULT virtual HeapObject* SlowAllocateRaw(int size_in_bytes);
friend class PageIterator;
};
class NumberAndSizeInfo BASE_EMBEDDED {
public:
NumberAndSizeInfo() : number_(0), bytes_(0) {}
int number() const { return number_; }
void increment_number(int num) { number_ += num; }
int bytes() const { return bytes_; }
void increment_bytes(int size) { bytes_ += size; }
void clear() {
number_ = 0;
bytes_ = 0;
}
private:
int number_;
int bytes_;
};
// HistogramInfo class for recording a single "bar" of a histogram. This
// class is used for collecting statistics to print to the log file.
class HistogramInfo: public NumberAndSizeInfo {
public:
HistogramInfo() : NumberAndSizeInfo() {}
const char* name() { return name_; }
void set_name(const char* name) { name_ = name; }
private:
const char* name_;
};
enum SemiSpaceId {
kFromSpace = 0,
kToSpace = 1
};
class SemiSpace;
class NewSpacePage : public MemoryChunk {
public:
// GC related flags copied from from-space to to-space when
// flipping semispaces.
static const intptr_t kCopyOnFlipFlagsMask =
(1 << MemoryChunk::POINTERS_TO_HERE_ARE_INTERESTING) |
(1 << MemoryChunk::POINTERS_FROM_HERE_ARE_INTERESTING) |
(1 << MemoryChunk::SCAN_ON_SCAVENGE);
static const int kAreaSize = Page::kNonCodeObjectAreaSize;
inline NewSpacePage* next_page() const {
return static_cast<NewSpacePage*>(next_chunk());
}
inline void set_next_page(NewSpacePage* page) {
set_next_chunk(page);
}
inline NewSpacePage* prev_page() const {
return static_cast<NewSpacePage*>(prev_chunk());
}
inline void set_prev_page(NewSpacePage* page) {
set_prev_chunk(page);
}
SemiSpace* semi_space() {
return reinterpret_cast<SemiSpace*>(owner());
}
bool is_anchor() { return !this->InNewSpace(); }
static bool IsAtStart(Address addr) {
return (reinterpret_cast<intptr_t>(addr) & Page::kPageAlignmentMask)
== kObjectStartOffset;
}
static bool IsAtEnd(Address addr) {
return (reinterpret_cast<intptr_t>(addr) & Page::kPageAlignmentMask) == 0;
}
Address address() {
return reinterpret_cast<Address>(this);
}
// Finds the NewSpacePage containg the given address.
static inline NewSpacePage* FromAddress(Address address_in_page) {
Address page_start =
reinterpret_cast<Address>(reinterpret_cast<uintptr_t>(address_in_page) &
~Page::kPageAlignmentMask);
NewSpacePage* page = reinterpret_cast<NewSpacePage*>(page_start);
return page;
}
// Find the page for a limit address. A limit address is either an address
// inside a page, or the address right after the last byte of a page.
static inline NewSpacePage* FromLimit(Address address_limit) {
return NewSpacePage::FromAddress(address_limit - 1);
}
private:
// Create a NewSpacePage object that is only used as anchor
// for the doubly-linked list of real pages.
explicit NewSpacePage(SemiSpace* owner) {
InitializeAsAnchor(owner);
}
static NewSpacePage* Initialize(Heap* heap,
Address start,
SemiSpace* semi_space);
// Intialize a fake NewSpacePage used as sentinel at the ends
// of a doubly-linked list of real NewSpacePages.
// Only uses the prev/next links, and sets flags to not be in new-space.
void InitializeAsAnchor(SemiSpace* owner);
friend class SemiSpace;
friend class SemiSpaceIterator;
};
// -----------------------------------------------------------------------------
// SemiSpace in young generation
//
// A semispace is a contiguous chunk of memory holding page-like memory
// chunks. The mark-compact collector uses the memory of the first page in
// the from space as a marking stack when tracing live objects.
class SemiSpace : public Space {
public:
// Constructor.
SemiSpace(Heap* heap, SemiSpaceId semispace)
: Space(heap, NEW_SPACE, NOT_EXECUTABLE),
start_(NULL),
age_mark_(NULL),
id_(semispace),
anchor_(this),
current_page_(NULL) { }
// Sets up the semispace using the given chunk.
void SetUp(Address start, int initial_capacity, int maximum_capacity);
// Tear down the space. Heap memory was not allocated by the space, so it
// is not deallocated here.
void TearDown();
// True if the space has been set up but not torn down.
bool HasBeenSetUp() { return start_ != NULL; }
// Grow the semispace to the new capacity. The new capacity
// requested must be larger than the current capacity and less than
// the maximum capacity.
bool GrowTo(int new_capacity);
// Shrinks the semispace to the new capacity. The new capacity
// requested must be more than the amount of used memory in the
// semispace and less than the current capacity.
bool ShrinkTo(int new_capacity);
// Returns the start address of the first page of the space.
Address space_start() {
ASSERT(anchor_.next_page() != &anchor_);
return anchor_.next_page()->area_start();
}
// Returns the start address of the current page of the space.
Address page_low() {
return current_page_->area_start();
}
// Returns one past the end address of the space.
Address space_end() {
return anchor_.prev_page()->area_end();
}
// Returns one past the end address of the current page of the space.
Address page_high() {
return current_page_->area_end();
}
bool AdvancePage() {
NewSpacePage* next_page = current_page_->next_page();
if (next_page == anchor()) return false;
current_page_ = next_page;
return true;
}
// Resets the space to using the first page.
void Reset();
// Age mark accessors.
Address age_mark() { return age_mark_; }
void set_age_mark(Address mark);
// True if the address is in the address range of this semispace (not
// necessarily below the allocation pointer).
bool Contains(Address a) {
return (reinterpret_cast<uintptr_t>(a) & address_mask_)
== reinterpret_cast<uintptr_t>(start_);
}
// True if the object is a heap object in the address range of this
// semispace (not necessarily below the allocation pointer).
bool Contains(Object* o) {
return (reinterpret_cast<uintptr_t>(o) & object_mask_) == object_expected_;
}
// If we don't have these here then SemiSpace will be abstract. However
// they should never be called.
virtual intptr_t Size() {
UNREACHABLE();
return 0;
}
virtual bool ReserveSpace(int bytes) {
UNREACHABLE();
return false;
}
bool is_committed() { return committed_; }
bool Commit();
bool Uncommit();
NewSpacePage* first_page() { return anchor_.next_page(); }
NewSpacePage* current_page() { return current_page_; }
#ifdef VERIFY_HEAP
virtual void Verify();
#endif
#ifdef DEBUG
virtual void Print();
// Validate a range of of addresses in a SemiSpace.
// The "from" address must be on a page prior to the "to" address,
// in the linked page order, or it must be earlier on the same page.
static void AssertValidRange(Address from, Address to);
#else
// Do nothing.
inline static void AssertValidRange(Address from, Address to) {}
#endif
// Returns the current capacity of the semi space.
int Capacity() { return capacity_; }
// Returns the maximum capacity of the semi space.
int MaximumCapacity() { return maximum_capacity_; }
// Returns the initial capacity of the semi space.
int InitialCapacity() { return initial_capacity_; }
SemiSpaceId id() { return id_; }
static void Swap(SemiSpace* from, SemiSpace* to);
private:
// Flips the semispace between being from-space and to-space.
// Copies the flags into the masked positions on all pages in the space.
void FlipPages(intptr_t flags, intptr_t flag_mask);
NewSpacePage* anchor() { return &anchor_; }
// The current and maximum capacity of the space.
int capacity_;
int maximum_capacity_;
int initial_capacity_;
// The start address of the space.
Address start_;
// Used to govern object promotion during mark-compact collection.
Address age_mark_;
// Masks and comparison values to test for containment in this semispace.
uintptr_t address_mask_;
uintptr_t object_mask_;
uintptr_t object_expected_;
bool committed_;
SemiSpaceId id_;
NewSpacePage anchor_;
NewSpacePage* current_page_;
friend class SemiSpaceIterator;
friend class NewSpacePageIterator;
public:
TRACK_MEMORY("SemiSpace")
};
// A SemiSpaceIterator is an ObjectIterator that iterates over the active
// semispace of the heap's new space. It iterates over the objects in the
// semispace from a given start address (defaulting to the bottom of the
// semispace) to the top of the semispace. New objects allocated after the
// iterator is created are not iterated.
class SemiSpaceIterator : public ObjectIterator {
public:
// Create an iterator over the objects in the given space. If no start
// address is given, the iterator starts from the bottom of the space. If
// no size function is given, the iterator calls Object::Size().
// Iterate over all of allocated to-space.
explicit SemiSpaceIterator(NewSpace* space);
// Iterate over all of allocated to-space, with a custome size function.
SemiSpaceIterator(NewSpace* space, HeapObjectCallback size_func);
// Iterate over part of allocated to-space, from start to the end
// of allocation.
SemiSpaceIterator(NewSpace* space, Address start);
// Iterate from one address to another in the same semi-space.
SemiSpaceIterator(Address from, Address to);
HeapObject* Next() {
if (current_ == limit_) return NULL;
if (NewSpacePage::IsAtEnd(current_)) {
NewSpacePage* page = NewSpacePage::FromLimit(current_);
page = page->next_page();
ASSERT(!page->is_anchor());
current_ = page->area_start();
if (current_ == limit_) return NULL;
}
HeapObject* object = HeapObject::FromAddress(current_);
int size = (size_func_ == NULL) ? object->Size() : size_func_(object);
current_ += size;
return object;
}
// Implementation of the ObjectIterator functions.
virtual HeapObject* next_object() { return Next(); }
private:
void Initialize(Address start,
Address end,
HeapObjectCallback size_func);
// The current iteration point.
Address current_;
// The end of iteration.
Address limit_;
// The callback function.
HeapObjectCallback size_func_;
};
// -----------------------------------------------------------------------------
// A PageIterator iterates the pages in a semi-space.
class NewSpacePageIterator BASE_EMBEDDED {
public:
// Make an iterator that runs over all pages in to-space.
explicit inline NewSpacePageIterator(NewSpace* space);
// Make an iterator that runs over all pages in the given semispace,
// even those not used in allocation.
explicit inline NewSpacePageIterator(SemiSpace* space);
// Make iterator that iterates from the page containing start
// to the page that contains limit in the same semispace.
inline NewSpacePageIterator(Address start, Address limit);
inline bool has_next();
inline NewSpacePage* next();
private:
NewSpacePage* prev_page_; // Previous page returned.
// Next page that will be returned. Cached here so that we can use this
// iterator for operations that deallocate pages.
NewSpacePage* next_page_;
// Last page returned.
NewSpacePage* last_page_;
};
// -----------------------------------------------------------------------------
// The young generation space.
//
// The new space consists of a contiguous pair of semispaces. It simply
// forwards most functions to the appropriate semispace.
class NewSpace : public Space {
public:
// Constructor.
explicit NewSpace(Heap* heap)
: Space(heap, NEW_SPACE, NOT_EXECUTABLE),
to_space_(heap, kToSpace),
from_space_(heap, kFromSpace),
reservation_(),
inline_allocation_limit_step_(0) {}
// Sets up the new space using the given chunk.
bool SetUp(int reserved_semispace_size_, int max_semispace_size);
// Tears down the space. Heap memory was not allocated by the space, so it
// is not deallocated here.
void TearDown();
// True if the space has been set up but not torn down.
bool HasBeenSetUp() {
return to_space_.HasBeenSetUp() && from_space_.HasBeenSetUp();
}
// Flip the pair of spaces.
void Flip();
// Grow the capacity of the semispaces. Assumes that they are not at
// their maximum capacity.
void Grow();
// Shrink the capacity of the semispaces.
void Shrink();
// True if the address or object lies in the address range of either
// semispace (not necessarily below the allocation pointer).
bool Contains(Address a) {
return (reinterpret_cast<uintptr_t>(a) & address_mask_)
== reinterpret_cast<uintptr_t>(start_);
}
bool Contains(Object* o) {
Address a = reinterpret_cast<Address>(o);
return (reinterpret_cast<uintptr_t>(a) & object_mask_) == object_expected_;
}
// Return the allocated bytes in the active semispace.
virtual intptr_t Size() {
return pages_used_ * NewSpacePage::kAreaSize +
static_cast<int>(top() - to_space_.page_low());
}
// The same, but returning an int. We have to have the one that returns
// intptr_t because it is inherited, but if we know we are dealing with the
// new space, which can't get as big as the other spaces then this is useful:
int SizeAsInt() { return static_cast<int>(Size()); }
// Return the current capacity of a semispace.
intptr_t EffectiveCapacity() {
SLOW_ASSERT(to_space_.Capacity() == from_space_.Capacity());
return (to_space_.Capacity() / Page::kPageSize) * NewSpacePage::kAreaSize;
}
// Return the current capacity of a semispace.
intptr_t Capacity() {
ASSERT(to_space_.Capacity() == from_space_.Capacity());
return to_space_.Capacity();
}
// Return the total amount of memory committed for new space.
intptr_t CommittedMemory() {
if (from_space_.is_committed()) return 2 * Capacity();
return Capacity();
}
// Return the available bytes without growing.
intptr_t Available() {
return Capacity() - Size();
}
// Return the maximum capacity of a semispace.
int MaximumCapacity() {
ASSERT(to_space_.MaximumCapacity() == from_space_.MaximumCapacity());
return to_space_.MaximumCapacity();
}
// Returns the initial capacity of a semispace.
int InitialCapacity() {
ASSERT(to_space_.InitialCapacity() == from_space_.InitialCapacity());
return to_space_.InitialCapacity();
}
// Return the address of the allocation pointer in the active semispace.
Address top() {
ASSERT(to_space_.current_page()->ContainsLimit(allocation_info_.top));
return allocation_info_.top;
}
// Return the address of the first object in the active semispace.
Address bottom() { return to_space_.space_start(); }
// Get the age mark of the inactive semispace.
Address age_mark() { return from_space_.age_mark(); }
// Set the age mark in the active semispace.
void set_age_mark(Address mark) { to_space_.set_age_mark(mark); }
// The start address of the space and a bit mask. Anding an address in the
// new space with the mask will result in the start address.
Address start() { return start_; }
uintptr_t mask() { return address_mask_; }
INLINE(uint32_t AddressToMarkbitIndex(Address addr)) {
ASSERT(Contains(addr));
ASSERT(IsAligned(OffsetFrom(addr), kPointerSize) ||
IsAligned(OffsetFrom(addr) - 1, kPointerSize));
return static_cast<uint32_t>(addr - start_) >> kPointerSizeLog2;
}
INLINE(Address MarkbitIndexToAddress(uint32_t index)) {
return reinterpret_cast<Address>(index << kPointerSizeLog2);
}
// The allocation top and limit addresses.
Address* allocation_top_address() { return &allocation_info_.top; }
Address* allocation_limit_address() { return &allocation_info_.limit; }
MUST_USE_RESULT INLINE(MaybeObject* AllocateRaw(int size_in_bytes));
// Reset the allocation pointer to the beginning of the active semispace.
void ResetAllocationInfo();
void LowerInlineAllocationLimit(intptr_t step) {
inline_allocation_limit_step_ = step;
if (step == 0) {
allocation_info_.limit = to_space_.page_high();
} else {
allocation_info_.limit = Min(
allocation_info_.top + inline_allocation_limit_step_,
allocation_info_.limit);
}
top_on_previous_step_ = allocation_info_.top;
}
// Get the extent of the inactive semispace (for use as a marking stack,
// or to zap it). Notice: space-addresses are not necessarily on the
// same page, so FromSpaceStart() might be above FromSpaceEnd().
Address FromSpacePageLow() { return from_space_.page_low(); }
Address FromSpacePageHigh() { return from_space_.page_high(); }
Address FromSpaceStart() { return from_space_.space_start(); }
Address FromSpaceEnd() { return from_space_.space_end(); }
// Get the extent of the active semispace's pages' memory.
Address ToSpaceStart() { return to_space_.space_start(); }
Address ToSpaceEnd() { return to_space_.space_end(); }
inline bool ToSpaceContains(Address address) {
return to_space_.Contains(address);
}
inline bool FromSpaceContains(Address address) {
return from_space_.Contains(address);
}
// True if the object is a heap object in the address range of the
// respective semispace (not necessarily below the allocation pointer of the
// semispace).
inline bool ToSpaceContains(Object* o) { return to_space_.Contains(o); }
inline bool FromSpaceContains(Object* o) { return from_space_.Contains(o); }
// Try to switch the active semispace to a new, empty, page.
// Returns false if this isn't possible or reasonable (i.e., there
// are no pages, or the current page is already empty), or true
// if successful.
bool AddFreshPage();
virtual bool ReserveSpace(int bytes);
// Resizes a sequential string which must be the most recent thing that was
// allocated in new space.
template <typename StringType>
inline void ShrinkStringAtAllocationBoundary(String* string, int len);
#ifdef VERIFY_HEAP
// Verify the active semispace.
virtual void Verify();
#endif
#ifdef DEBUG
// Print the active semispace.
virtual void Print() { to_space_.Print(); }
#endif
// Iterates the active semispace to collect statistics.
void CollectStatistics();
// Reports previously collected statistics of the active semispace.
void ReportStatistics();
// Clears previously collected statistics.
void ClearHistograms();
// Record the allocation or promotion of a heap object. Note that we don't
// record every single allocation, but only those that happen in the
// to space during a scavenge GC.
void RecordAllocation(HeapObject* obj);
void RecordPromotion(HeapObject* obj);
// Return whether the operation succeded.
bool CommitFromSpaceIfNeeded() {
if (from_space_.is_committed()) return true;
return from_space_.Commit();
}
bool UncommitFromSpace() {
if (!from_space_.is_committed()) return true;
return from_space_.Uncommit();
}
inline intptr_t inline_allocation_limit_step() {
return inline_allocation_limit_step_;
}
SemiSpace* active_space() { return &to_space_; }
private:
// Update allocation info to match the current to-space page.
void UpdateAllocationInfo();
Address chunk_base_;
uintptr_t chunk_size_;
// The semispaces.
SemiSpace to_space_;
SemiSpace from_space_;
VirtualMemory reservation_;
int pages_used_;
// Start address and bit mask for containment testing.
Address start_;
uintptr_t address_mask_;
uintptr_t object_mask_;
uintptr_t object_expected_;
// Allocation pointer and limit for normal allocation and allocation during
// mark-compact collection.
AllocationInfo allocation_info_;
// When incremental marking is active we will set allocation_info_.limit
// to be lower than actual limit and then will gradually increase it
// in steps to guarantee that we do incremental marking steps even
// when all allocation is performed from inlined generated code.
intptr_t inline_allocation_limit_step_;
Address top_on_previous_step_;
HistogramInfo* allocated_histogram_;
HistogramInfo* promoted_histogram_;
MUST_USE_RESULT MaybeObject* SlowAllocateRaw(int size_in_bytes);
friend class SemiSpaceIterator;
public:
TRACK_MEMORY("NewSpace")
};
// -----------------------------------------------------------------------------
// Old object space (excluding map objects)
class OldSpace : public PagedSpace {
public:
// Creates an old space object with a given maximum capacity.
// The constructor does not allocate pages from OS.
OldSpace(Heap* heap,
intptr_t max_capacity,
AllocationSpace id,
Executability executable)
: PagedSpace(heap, max_capacity, id, executable) {
page_extra_ = 0;
}
// The limit of allocation for a page in this space.
virtual Address PageAllocationLimit(Page* page) {
return page->area_end();
}
public:
TRACK_MEMORY("OldSpace")
};
// For contiguous spaces, top should be in the space (or at the end) and limit
// should be the end of the space.
#define ASSERT_SEMISPACE_ALLOCATION_INFO(info, space) \
SLOW_ASSERT((space).page_low() <= (info).top \
&& (info).top <= (space).page_high() \
&& (info).limit <= (space).page_high())
// -----------------------------------------------------------------------------
// Old space for objects of a fixed size
class FixedSpace : public PagedSpace {
public:
FixedSpace(Heap* heap,
intptr_t max_capacity,
AllocationSpace id,
int object_size_in_bytes,
const char* name)
: PagedSpace(heap, max_capacity, id, NOT_EXECUTABLE),
object_size_in_bytes_(object_size_in_bytes),
name_(name) {
page_extra_ = Page::kNonCodeObjectAreaSize % object_size_in_bytes;
}
// The limit of allocation for a page in this space.
virtual Address PageAllocationLimit(Page* page) {
return page->area_end() - page_extra_;
}
int object_size_in_bytes() { return object_size_in_bytes_; }
// Prepares for a mark-compact GC.
virtual void PrepareForMarkCompact();
private:
// The size of objects in this space.
int object_size_in_bytes_;
// The name of this space.
const char* name_;
};
// -----------------------------------------------------------------------------
// Old space for all map objects
class MapSpace : public FixedSpace {
public:
// Creates a map space object with a maximum capacity.
MapSpace(Heap* heap, intptr_t max_capacity, AllocationSpace id)
: FixedSpace(heap, max_capacity, id, Map::kSize, "map"),
max_map_space_pages_(kMaxMapPageIndex - 1) {
}
// Given an index, returns the page address.
// TODO(1600): this limit is artifical just to keep code compilable
static const int kMaxMapPageIndex = 1 << 16;
virtual int RoundSizeDownToObjectAlignment(int size) {
if (IsPowerOf2(Map::kSize)) {
return RoundDown(size, Map::kSize);
} else {
return (size / Map::kSize) * Map::kSize;
}
}
protected:
virtual void VerifyObject(HeapObject* obj);
private:
static const int kMapsPerPage = Page::kNonCodeObjectAreaSize / Map::kSize;
// Do map space compaction if there is a page gap.
int CompactionThreshold() {
return kMapsPerPage * (max_map_space_pages_ - 1);
}
const int max_map_space_pages_;
public:
TRACK_MEMORY("MapSpace")
};
// -----------------------------------------------------------------------------
// Old space for all global object property cell objects
class CellSpace : public FixedSpace {
public:
// Creates a property cell space object with a maximum capacity.
CellSpace(Heap* heap, intptr_t max_capacity, AllocationSpace id)
: FixedSpace(heap, max_capacity, id, JSGlobalPropertyCell::kSize, "cell")
{}
virtual int RoundSizeDownToObjectAlignment(int size) {
if (IsPowerOf2(JSGlobalPropertyCell::kSize)) {
return RoundDown(size, JSGlobalPropertyCell::kSize);
} else {
return (size / JSGlobalPropertyCell::kSize) * JSGlobalPropertyCell::kSize;
}
}
protected:
virtual void VerifyObject(HeapObject* obj);
public:
TRACK_MEMORY("CellSpace")
};
// -----------------------------------------------------------------------------
// Large objects ( > Page::kMaxHeapObjectSize ) are allocated and managed by
// the large object space. A large object is allocated from OS heap with
// extra padding bytes (Page::kPageSize + Page::kObjectStartOffset).
// A large object always starts at Page::kObjectStartOffset to a page.
// Large objects do not move during garbage collections.
class LargeObjectSpace : public Space {
public:
LargeObjectSpace(Heap* heap, intptr_t max_capacity, AllocationSpace id);
virtual ~LargeObjectSpace() {}
// Initializes internal data structures.
bool SetUp();
// Releases internal resources, frees objects in this space.
void TearDown();
static intptr_t ObjectSizeFor(intptr_t chunk_size) {
if (chunk_size <= (Page::kPageSize + Page::kObjectStartOffset)) return 0;
return chunk_size - Page::kPageSize - Page::kObjectStartOffset;
}
// Shared implementation of AllocateRaw, AllocateRawCode and
// AllocateRawFixedArray.
MUST_USE_RESULT MaybeObject* AllocateRaw(int object_size,
Executability executable);
// Available bytes for objects in this space.
inline intptr_t Available();
virtual intptr_t Size() {
return size_;
}
virtual intptr_t SizeOfObjects() {
return objects_size_;
}
intptr_t CommittedMemory() {
return Size();
}
int PageCount() {
return page_count_;
}
// Finds an object for a given address, returns Failure::Exception()
// if it is not found. The function iterates through all objects in this
// space, may be slow.
MaybeObject* FindObject(Address a);
// Finds a large object page containing the given address, returns NULL
// if such a page doesn't exist.
LargePage* FindPage(Address a);
// Frees unmarked objects.
void FreeUnmarkedObjects();
// Checks whether a heap object is in this space; O(1).
bool Contains(HeapObject* obj);
// Checks whether the space is empty.
bool IsEmpty() { return first_page_ == NULL; }
// See the comments for ReserveSpace in the Space class. This has to be
// called after ReserveSpace has been called on the paged spaces, since they
// may use some memory, leaving less for large objects.
virtual bool ReserveSpace(int bytes);
LargePage* first_page() { return first_page_; }
#ifdef VERIFY_HEAP
virtual void Verify();
#endif
#ifdef DEBUG
virtual void Print();
void ReportStatistics();
void CollectCodeStatistics();
#endif
// Checks whether an address is in the object area in this space. It
// iterates all objects in the space. May be slow.
bool SlowContains(Address addr) { return !FindObject(addr)->IsFailure(); }
private:
intptr_t max_capacity_;
// The head of the linked list of large object chunks.
LargePage* first_page_;
intptr_t size_; // allocated bytes
int page_count_; // number of chunks
intptr_t objects_size_; // size of objects
// Map MemoryChunk::kAlignment-aligned chunks to large pages covering them
HashMap chunk_map_;
friend class LargeObjectIterator;
public:
TRACK_MEMORY("LargeObjectSpace")
};
class LargeObjectIterator: public ObjectIterator {
public:
explicit LargeObjectIterator(LargeObjectSpace* space);
LargeObjectIterator(LargeObjectSpace* space, HeapObjectCallback size_func);
HeapObject* Next();
// implementation of ObjectIterator.
virtual HeapObject* next_object() { return Next(); }
private:
LargePage* current_;
HeapObjectCallback size_func_;
};
// Iterates over the chunks (pages and large object pages) that can contain
// pointers to new space.
class PointerChunkIterator BASE_EMBEDDED {
public:
inline explicit PointerChunkIterator(Heap* heap);
// Return NULL when the iterator is done.
MemoryChunk* next() {
switch (state_) {
case kOldPointerState: {
if (old_pointer_iterator_.has_next()) {
return old_pointer_iterator_.next();
}
state_ = kMapState;
// Fall through.
}
case kMapState: {
if (map_iterator_.has_next()) {
return map_iterator_.next();
}
state_ = kLargeObjectState;
// Fall through.
}
case kLargeObjectState: {
HeapObject* heap_object;
do {
heap_object = lo_iterator_.Next();
if (heap_object == NULL) {
state_ = kFinishedState;
return NULL;
}
// Fixed arrays are the only pointer-containing objects in large
// object space.
} while (!heap_object->IsFixedArray());
MemoryChunk* answer = MemoryChunk::FromAddress(heap_object->address());
return answer;
}
case kFinishedState:
return NULL;
default:
break;
}
UNREACHABLE();
return NULL;
}
private:
enum State {
kOldPointerState,
kMapState,
kLargeObjectState,
kFinishedState
};
State state_;
PageIterator old_pointer_iterator_;
PageIterator map_iterator_;
LargeObjectIterator lo_iterator_;
};
#ifdef DEBUG
struct CommentStatistic {
const char* comment;
int size;
int count;
void Clear() {
comment = NULL;
size = 0;
count = 0;
}
// Must be small, since an iteration is used for lookup.
static const int kMaxComments = 64;
};
#endif
} } // namespace v8::internal
#endif // V8_SPACES_H_
|