# HG changeset patch # User lana # Date 1336675676 25200 # Node ID fa5227d43363dd36c19751fca5f5fde0ac7eeaa5 # Parent e0d32945f6abdc9d15ce228024ded43b4453c96d# Parent 4cc5610a6dd6227da766ebf9742eb11ff5ded6c0 Merge diff -r e0d32945f6ab -r fa5227d43363 .hgtags --- a/.hgtags Thu May 10 20:05:12 2012 +0400 +++ b/.hgtags Thu May 10 11:47:56 2012 -0700 @@ -157,3 +157,5 @@ a6e6d42203e6d35f9e8b31eac25b0021b4dd58ad jdk8-b33 0ae89825c75c9492e44efb3aca3d9ee3d8a209df jdk8-b34 f151d5833912a82cd4f203944da0305c3be83ecc jdk8-b35 +98ce9816ae089c959ba1e70fba98423a31c4e9fa jdk8-b36 +b3a91113026c99b0da010d41055719ab0d8938f0 jdk8-b37 diff -r e0d32945f6ab -r fa5227d43363 .hgtags-top-repo --- a/.hgtags-top-repo Thu May 10 20:05:12 2012 +0400 +++ b/.hgtags-top-repo Thu May 10 11:47:56 2012 -0700 @@ -157,3 +157,5 @@ 42f275168fa5d9e7c70b246614dca8cf81f52c2e jdk8-b33 894a478d2c4819a1a0f230bd7bdd09f3b2de9a8c jdk8-b34 5285317ebb4e8e4f6d8d52b5616fa801e2ea844d jdk8-b35 +6a6ba0a07f33d37a2f97b1107e60c6a9a69ec84d jdk8-b36 +b2972095a4b1e2a97409b7c3df61f3b263a5ce14 jdk8-b37 diff -r e0d32945f6ab -r fa5227d43363 README-builds.html --- a/README-builds.html Thu May 10 20:05:12 2012 +0400 +++ b/README-builds.html Thu May 10 11:47:56 2012 -0700 @@ -65,6 +65,7 @@

Basic Mac OS X System Setup

Build Dependencies

Bootstrap JDK

@@ -951,6 +958,36 @@

Basic Mac OS X System Setup

+ X64 only: + The minimum recommended hardware for building + the Mac OS X version is any 64-bit capable Intel processor, at least 2 + GB of RAM, and approximately 3 GB of free disk space. You should also + have OS X Lion 10.7.3 installed. +

Basic Mac OS X Check List

+
+
+ Install XCode 4.1 or newer. + If you install XCode 4.3 or newer, make sure you also install + "Command line tools" found under the preferences pane "Downloads". +
+
+ Install "Java for OS X Lion Update 1", + set ALT_BOOTDIR to `/usr/libexec/java_home -v 1.6` +
+
+ Optional Import JDK, set + ALT_JDK_IMPORT_PATH. +
+
+

Build Dependencies

Depending on the platform, the OpenJDK build process has some basic @@ -1194,6 +1231,10 @@ set INCLUDE=%VSINSTALLDIR%\vc\include;%WindowsSdkDir%\include set LIB=%VSINSTALLDIR%\vc\lib\amd64;%WindowsSdkDir%\lib\x64 + OS X Lion 10.7.3: LLVM GCC +
+ LLVM GCC is bundled with XCode. The version should be at least 4.2.1. +

Zip and Unzip

.debuginfo .so - # BFD: stKPaiop: Not enough room for program headers, try linking with -N - # /usr/sfw/bin/gobjcopy: stKPaiop: Bad value - # BFD: stKPaiop: Not enough room for program headers, try linking with -N - # /usr/sfw/bin/gobjcopy: libsaproc.debuginfo: Bad value - # BFD: stKPaiop: Not enough room for program headers, try linking with -N - # /usr/sfw/bin/gobjcopy: stKPaiop: Bad value - _JUNK_ := $(shell \ - echo >&2 "INFO: $(DEF_OBJCOPY) is not working on Solaris AMD64/X64") + # Disable FULL_DEBUG_SYMBOLS by default because dtrace tests are + # failing in nightly when the debug info files are ZIP'ed. On + # Solaris debug info files need to be ZIP'ed to reduce the impact + # on disk space footprint. + FULL_DEBUG_SYMBOLS ?= 0 + ifeq ($(BUILD_FLAVOR), product) + # FULL_DEBUG_SYMBOLS ?= 1 + ENABLE_FULL_DEBUG_SYMBOLS = $(FULL_DEBUG_SYMBOLS) + else + # debug variants always get Full Debug Symbols (if available) + # ENABLE_FULL_DEBUG_SYMBOLS = 1 + ENABLE_FULL_DEBUG_SYMBOLS = $(FULL_DEBUG_SYMBOLS) + endif + _JUNK_ := $(shell \ + echo >&2 "INFO: ENABLE_FULL_DEBUG_SYMBOLS=$(ENABLE_FULL_DEBUG_SYMBOLS)") + # since objcopy is optional, we set ZIP_DEBUGINFO_FILES later + + ifeq ($(ENABLE_FULL_DEBUG_SYMBOLS),1) + # Default OBJCOPY comes from the SUNWbinutils package: + DEF_OBJCOPY=/usr/sfw/bin/gobjcopy + ifeq ($(VM_PLATFORM),solaris_amd64) + # On Solaris AMD64/X64, gobjcopy is not happy and fails: + # + # usr/sfw/bin/gobjcopy --add-gnu-debuglink=.debuginfo .so + # BFD: stKPaiop: Not enough room for program headers, try linking with -N + # /usr/sfw/bin/gobjcopy: stKPaiop: Bad value + # BFD: stKPaiop: Not enough room for program headers, try linking with -N + # /usr/sfw/bin/gobjcopy: libsaproc.debuginfo: Bad value + # BFD: stKPaiop: Not enough room for program headers, try linking with -N + # /usr/sfw/bin/gobjcopy: stKPaiop: Bad value + _JUNK_ := $(shell \ + echo >&2 "INFO: $(DEF_OBJCOPY) is not working on Solaris AMD64/X64") + OBJCOPY= + else + OBJCOPY=$(shell test -x $(DEF_OBJCOPY) && echo $(DEF_OBJCOPY)) + ifneq ($(ALT_OBJCOPY),) + _JUNK_ := $(shell echo >&2 "INFO: ALT_OBJCOPY=$(ALT_OBJCOPY)") + OBJCOPY=$(shell test -x $(ALT_OBJCOPY) && echo $(ALT_OBJCOPY)) + endif + endif + else OBJCOPY= - else - OBJCOPY=$(shell test -x $(DEF_OBJCOPY) && echo $(DEF_OBJCOPY)) - ifneq ($(ALT_OBJCOPY),) - _JUNK_ := $(shell echo >&2 "INFO: ALT_OBJCOPY=$(ALT_OBJCOPY)") - # disable .debuginfo support by setting ALT_OBJCOPY to a non-existent path - OBJCOPY=$(shell test -x $(ALT_OBJCOPY) && echo $(ALT_OBJCOPY)) - endif endif -endif - + ifeq ($(OBJCOPY),) _JUNK_ := $(shell \ echo >&2 "INFO: no objcopy cmd found so cannot create .debuginfo files.") + ENABLE_FULL_DEBUG_SYMBOLS=0 + _JUNK_ := $(shell \ + echo >&2 "INFO: ENABLE_FULL_DEBUG_SYMBOLS=$(ENABLE_FULL_DEBUG_SYMBOLS)") else _JUNK_ := $(shell \ echo >&2 "INFO: $(OBJCOPY) cmd found so will create .debuginfo files.") - + # Library stripping policies for .debuginfo configs: # all_strip - strips everything from the library # min_strip - strips most stuff from the library; leaves minimum symbols @@ -133,14 +171,19 @@ # Oracle security policy requires "all_strip". A waiver was granted on # 2011.09.01 that permits using "min_strip" in the Java JDK and Java JRE. # - DEF_STRIP_POLICY="min_strip" - ifeq ($(ALT_STRIP_POLICY),) - STRIP_POLICY=$(DEF_STRIP_POLICY) - else - STRIP_POLICY=$(ALT_STRIP_POLICY) - endif + # Currently, STRIP_POLICY is only used when Full Debug Symbols is enabled. + # + STRIP_POLICY ?= min_strip + _JUNK_ := $(shell \ echo >&2 "INFO: STRIP_POLICY=$(STRIP_POLICY)") + + # Disable ZIP_DEBUGINFO_FILES by default because dtrace tests are + # failing in nightly when the debug info files are ZIP'ed. + ZIP_DEBUGINFO_FILES ?= 0 + + _JUNK_ := $(shell \ + echo >&2 "INFO: ZIP_DEBUGINFO_FILES=$(ZIP_DEBUGINFO_FILES)") endif endif @@ -156,8 +199,12 @@ # client and server subdirectories have symbolic links to ../libjsig.$(LIBRARY_SUFFIX) EXPORT_LIST += $(EXPORT_JRE_LIB_ARCH_DIR)/libjsig.$(LIBRARY_SUFFIX) -ifneq ($(OBJCOPY),) - EXPORT_LIST += $(EXPORT_JRE_LIB_ARCH_DIR)/libjsig.debuginfo +ifeq ($(ENABLE_FULL_DEBUG_SYMBOLS),1) + ifeq ($(ZIP_DEBUGINFO_FILES),1) + EXPORT_LIST += $(EXPORT_JRE_LIB_ARCH_DIR)/libjsig.diz + else + EXPORT_LIST += $(EXPORT_JRE_LIB_ARCH_DIR)/libjsig.debuginfo + endif endif EXPORT_LIST += $(EXPORT_JRE_LIB_DIR)/wb.jar @@ -174,10 +221,16 @@ EXPORT_LIST += $(EXPORT_SERVER_DIR)/64/libjvm_db.$(LIBRARY_SUFFIX) EXPORT_LIST += $(EXPORT_SERVER_DIR)/64/libjvm_dtrace.$(LIBRARY_SUFFIX) endif - ifneq ($(OBJCOPY),) - EXPORT_LIST += $(EXPORT_SERVER_DIR)/libjvm.debuginfo - EXPORT_LIST += $(EXPORT_SERVER_DIR)/libjvm_db.debuginfo - EXPORT_LIST += $(EXPORT_SERVER_DIR)/libjvm_dtrace.debuginfo + ifeq ($(ENABLE_FULL_DEBUG_SYMBOLS),1) + ifeq ($(ZIP_DEBUGINFO_FILES),1) + EXPORT_LIST += $(EXPORT_SERVER_DIR)/libjvm.diz + EXPORT_LIST += $(EXPORT_SERVER_DIR)/libjvm_db.diz + EXPORT_LIST += $(EXPORT_SERVER_DIR)/libjvm_dtrace.diz + else + EXPORT_LIST += $(EXPORT_SERVER_DIR)/libjvm.debuginfo + EXPORT_LIST += $(EXPORT_SERVER_DIR)/libjvm_db.debuginfo + EXPORT_LIST += $(EXPORT_SERVER_DIR)/libjvm_dtrace.debuginfo + endif endif endif ifeq ($(JVM_VARIANT_CLIENT),true) @@ -189,19 +242,33 @@ EXPORT_LIST += $(EXPORT_CLIENT_DIR)/64/libjvm_db.$(LIBRARY_SUFFIX) EXPORT_LIST += $(EXPORT_CLIENT_DIR)/64/libjvm_dtrace.$(LIBRARY_SUFFIX) endif - ifneq ($(OBJCOPY),) - EXPORT_LIST += $(EXPORT_CLIENT_DIR)/libjvm.debuginfo - EXPORT_LIST += $(EXPORT_CLIENT_DIR)/libjvm_db.debuginfo - EXPORT_LIST += $(EXPORT_CLIENT_DIR)/libjvm_dtrace.debuginfo - ifeq ($(ARCH_DATA_MODEL),32) - EXPORT_LIST += $(EXPORT_CLIENT_DIR)/64/libjvm_db.debuginfo - EXPORT_LIST += $(EXPORT_CLIENT_DIR)/64/libjvm_dtrace.debuginfo + ifeq ($(ENABLE_FULL_DEBUG_SYMBOLS),1) + ifeq ($(ZIP_DEBUGINFO_FILES),1) + EXPORT_LIST += $(EXPORT_CLIENT_DIR)/libjvm.diz + EXPORT_LIST += $(EXPORT_CLIENT_DIR)/libjvm_db.diz + EXPORT_LIST += $(EXPORT_CLIENT_DIR)/libjvm_dtrace.diz + ifeq ($(ARCH_DATA_MODEL),32) + EXPORT_LIST += $(EXPORT_CLIENT_DIR)/64/libjvm_db.diz + EXPORT_LIST += $(EXPORT_CLIENT_DIR)/64/libjvm_dtrace.diz + endif + else + EXPORT_LIST += $(EXPORT_CLIENT_DIR)/libjvm.debuginfo + EXPORT_LIST += $(EXPORT_CLIENT_DIR)/libjvm_db.debuginfo + EXPORT_LIST += $(EXPORT_CLIENT_DIR)/libjvm_dtrace.debuginfo + ifeq ($(ARCH_DATA_MODEL),32) + EXPORT_LIST += $(EXPORT_CLIENT_DIR)/64/libjvm_db.debuginfo + EXPORT_LIST += $(EXPORT_CLIENT_DIR)/64/libjvm_dtrace.debuginfo + endif endif endif endif EXPORT_LIST += $(EXPORT_JRE_LIB_ARCH_DIR)/libsaproc.$(LIBRARY_SUFFIX) -ifneq ($(OBJCOPY),) - EXPORT_LIST += $(EXPORT_JRE_LIB_ARCH_DIR)/libsaproc.debuginfo +ifeq ($(ENABLE_FULL_DEBUG_SYMBOLS),1) + ifeq ($(ZIP_DEBUGINFO_FILES),1) + EXPORT_LIST += $(EXPORT_JRE_LIB_ARCH_DIR)/libsaproc.diz + else + EXPORT_LIST += $(EXPORT_JRE_LIB_ARCH_DIR)/libsaproc.debuginfo + endif endif EXPORT_LIST += $(EXPORT_LIB_DIR)/sa-jdi.jar diff -r e0d32945f6ab -r fa5227d43363 hotspot/make/solaris/makefiles/dtrace.make --- a/hotspot/make/solaris/makefiles/dtrace.make Thu May 10 20:05:12 2012 +0400 +++ b/hotspot/make/solaris/makefiles/dtrace.make Thu May 10 11:47:56 2012 -0700 @@ -1,5 +1,5 @@ # -# Copyright (c) 2005, 2011, Oracle and/or its affiliates. All rights reserved. +# Copyright (c) 2005, 2012, Oracle and/or its affiliates. All rights reserved. # DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. # # This code is free software; you can redistribute it and/or modify it @@ -41,15 +41,19 @@ LIBJVM_DB = libjvm_db.so LIBJVM_DB_G = libjvm$(G_SUFFIX)_db.so -LIBJVM_DB_DEBUGINFO = libjvm_db.debuginfo +LIBJVM_DB_DEBUGINFO = libjvm_db.debuginfo +LIBJVM_DB_DIZ = libjvm_db.diz LIBJVM_DB_G_DEBUGINFO = libjvm$(G_SUFFIX)_db.debuginfo +LIBJVM_DB_G_DIZ = libjvm$(G_SUFFIX)_db.diz JVM_DTRACE = jvm_dtrace LIBJVM_DTRACE = libjvm_dtrace.so LIBJVM_DTRACE_G = libjvm$(G_SUFFIX)_dtrace.so -LIBJVM_DTRACE_DEBUGINFO = libjvm_dtrace.debuginfo +LIBJVM_DTRACE_DEBUGINFO = libjvm_dtrace.debuginfo +LIBJVM_DTRACE_DIZ = libjvm_dtrace.diz LIBJVM_DTRACE_G_DEBUGINFO = libjvm$(G_SUFFIX)_dtrace.debuginfo +LIBJVM_DTRACE_G_DIZ = libjvm$(G_SUFFIX)_dtrace.diz JVMOFFS = JvmOffsets JVMOFFS.o = $(JVMOFFS).o @@ -95,10 +99,14 @@ XLIBJVM_DTRACE = 64/$(LIBJVM_DTRACE) XLIBJVM_DTRACE_G = 64/$(LIBJVM_DTRACE_G) -XLIBJVM_DB_DEBUGINFO = 64/$(LIBJVM_DB_DEBUGINFO) -XLIBJVM_DB_G_DEBUGINFO = 64/$(LIBJVM_DB_G_DEBUGINFO) -XLIBJVM_DTRACE_DEBUGINFO = 64/$(LIBJVM_DTRACE_DEBUGINFO) +XLIBJVM_DB_DEBUGINFO = 64/$(LIBJVM_DB_DEBUGINFO) +XLIBJVM_DB_DIZ = 64/$(LIBJVM_DB_DIZ) +XLIBJVM_DB_G_DEBUGINFO = 64/$(LIBJVM_DB_G_DEBUGINFO) +XLIBJVM_DB_G_DIZ = 64/$(LIBJVM_DB_G_DIZ) +XLIBJVM_DTRACE_DEBUGINFO = 64/$(LIBJVM_DTRACE_DEBUGINFO) +XLIBJVM_DTRACE_DIZ = 64/$(LIBJVM_DTRACE_DIZ) XLIBJVM_DTRACE_G_DEBUGINFO = 64/$(LIBJVM_DTRACE_G_DEBUGINFO) +XLIBJVM_DTRACE_G_DIZ = 64/$(LIBJVM_DTRACE_G_DIZ) $(XLIBJVM_DB): $(DTRACE_SRCDIR)/$(JVM_DB).c $(JVMOFFS).h $(LIBJVM_DB_MAPFILE) @echo Making $@ @@ -106,7 +114,7 @@ $(CC) $(SYMFLAG) $(ARCHFLAG/$(ISA)) -D$(TYPE) -I. -I$(GENERATED) \ $(SHARED_FLAG) $(LFLAGS_JVM_DB) -o $@ $(DTRACE_SRCDIR)/$(JVM_DB).c -lc [ -f $(XLIBJVM_DB_G) ] || { ln -s $(LIBJVM_DB) $(XLIBJVM_DB_G); } -ifneq ($(OBJCOPY),) +ifeq ($(ENABLE_FULL_DEBUG_SYMBOLS),1) $(QUIETLY) $(OBJCOPY) --only-keep-debug $@ $(XLIBJVM_DB_DEBUGINFO) $(QUIETLY) $(OBJCOPY) --add-gnu-debuglink=$(XLIBJVM_DB_DEBUGINFO) $@ ifeq ($(STRIP_POLICY),all_strip) @@ -117,7 +125,12 @@ # implied else here is no stripping at all endif endif - [ -f $(XLIBJVM_DB_G_DEBUGINFO) ] || { ln -s $(LIBJVM_DB_DEBUGINFO) $(XLIBJVM_DB_G_DEBUGINFO); } + [ -f $(XLIBJVM_DB_G_DEBUGINFO) ] || { ln -s $(XLIBJVM_DB_DEBUGINFO) $(XLIBJVM_DB_G_DEBUGINFO); } + ifeq ($(ZIP_DEBUGINFO_FILES),1) + $(ZIPEXE) -q -y $(XLIBJVM_DB_DIZ) $(XLIBJVM_DB_DEBUGINFO) $(XLIBJVM_DB_G_DEBUGINFO) + $(RM) $(XLIBJVM_DB_DEBUGINFO) $(XLIBJVM_DB_G_DEBUGINFO) + [ -f $(XLIBJVM_DB_G_DIZ) ] || { ln -s $(XLIBJVM_DB_DIZ) $(XLIBJVM_DB_G_DIZ); } + endif endif $(XLIBJVM_DTRACE): $(DTRACE_SRCDIR)/$(JVM_DTRACE).c $(DTRACE_SRCDIR)/$(JVM_DTRACE).h $(LIBJVM_DTRACE_MAPFILE) @@ -126,7 +139,7 @@ $(CC) $(SYMFLAG) $(ARCHFLAG/$(ISA)) -D$(TYPE) -I. \ $(SHARED_FLAG) $(LFLAGS_JVM_DTRACE) -o $@ $(DTRACE_SRCDIR)/$(JVM_DTRACE).c -lc -lthread -ldoor [ -f $(XLIBJVM_DTRACE_G) ] || { ln -s $(LIBJVM_DTRACE) $(XLIBJVM_DTRACE_G); } -ifneq ($(OBJCOPY),) +ifeq ($(ENABLE_FULL_DEBUG_SYMBOLS),1) $(QUIETLY) $(OBJCOPY) --only-keep-debug $@ $(XLIBJVM_DTRACE_DEBUGINFO) $(QUIETLY) $(OBJCOPY) --add-gnu-debuglink=$(XLIBJVM_DTRACE_DEBUGINFO) $@ ifeq ($(STRIP_POLICY),all_strip) @@ -137,7 +150,12 @@ # implied else here is no stripping at all endif endif - [ -f $(XLIBJVM_DTRACE_G_DEBUGINFO) ] || { ln -s $(LIBJVM_DTRACE_DEBUGINFO) $(XLIBJVM_DTRACE_G_DEBUGINFO); } + [ -f $(XLIBJVM_DTRACE_G_DEBUGINFO) ] || { ln -s $(XLIBJVM_DTRACE_DEBUGINFO) $(XLIBJVM_DTRACE_G_DEBUGINFO); } + ifeq ($(ZIP_DEBUGINFO_FILES),1) + $(ZIPEXE) -q -y $(XLIBJVM_DTRACE_DIZ) $(XLIBJVM_DTRACE_DEBUGINFO) $(XLIBJVM_DTRACE_G_DEBUGINFO) + $(RM) $(XLIBJVM_DTRACE_DEBUGINFO) $(XLIBJVM_DTRACE_G_DEBUGINFO) + [ -f $(XLIBJVM_DTRACE_G_DIZ) ] || { ln -s $(XLIBJVM_DTRACE_DIZ) $(XLIBJVM_DTRACE_G_DIZ); } + endif endif endif # ifneq ("${ISA}","${BUILDARCH}") @@ -185,7 +203,7 @@ $(QUIETLY) $(CC) $(SYMFLAG) $(ARCHFLAG) -D$(TYPE) -I. -I$(GENERATED) \ $(SHARED_FLAG) $(LFLAGS_JVM_DB) -o $@ $(DTRACE_SRCDIR)/$(JVM_DB).c -lc [ -f $(LIBJVM_DB_G) ] || { ln -s $@ $(LIBJVM_DB_G); } -ifneq ($(OBJCOPY),) +ifeq ($(ENABLE_FULL_DEBUG_SYMBOLS),1) $(QUIETLY) $(OBJCOPY) --only-keep-debug $@ $(LIBJVM_DB_DEBUGINFO) $(QUIETLY) $(OBJCOPY) --add-gnu-debuglink=$(LIBJVM_DB_DEBUGINFO) $@ ifeq ($(STRIP_POLICY),all_strip) @@ -197,6 +215,11 @@ endif endif [ -f $(LIBJVM_DB_G_DEBUGINFO) ] || { ln -s $(LIBJVM_DB_DEBUGINFO) $(LIBJVM_DB_G_DEBUGINFO); } + ifeq ($(ZIP_DEBUGINFO_FILES),1) + $(ZIPEXE) -q -y $(LIBJVM_DB_DIZ) $(LIBJVM_DB_DEBUGINFO) $(LIBJVM_DB_G_DEBUGINFO) + $(RM) $(LIBJVM_DB_DEBUGINFO) $(LIBJVM_DB_G_DEBUGINFO) + [ -f $(LIBJVM_DB_G_DIZ) ] || { ln -s $(LIBJVM_DB_DIZ) $(LIBJVM_DB_G_DIZ); } + endif endif $(LIBJVM_DTRACE): $(DTRACE_SRCDIR)/$(JVM_DTRACE).c $(XLIBJVM_DTRACE) $(DTRACE_SRCDIR)/$(JVM_DTRACE).h $(LIBJVM_DTRACE_MAPFILE) @@ -204,7 +227,7 @@ $(QUIETLY) $(CC) $(SYMFLAG) $(ARCHFLAG) -D$(TYPE) -I. \ $(SHARED_FLAG) $(LFLAGS_JVM_DTRACE) -o $@ $(DTRACE_SRCDIR)/$(JVM_DTRACE).c -lc -lthread -ldoor [ -f $(LIBJVM_DTRACE_G) ] || { ln -s $@ $(LIBJVM_DTRACE_G); } -ifneq ($(OBJCOPY),) +ifeq ($(ENABLE_FULL_DEBUG_SYMBOLS),1) $(QUIETLY) $(OBJCOPY) --only-keep-debug $@ $(LIBJVM_DTRACE_DEBUGINFO) $(QUIETLY) $(OBJCOPY) --add-gnu-debuglink=$(LIBJVM_DTRACE_DEBUGINFO) $@ ifeq ($(STRIP_POLICY),all_strip) @@ -216,6 +239,11 @@ endif endif [ -f $(LIBJVM_DTRACE_G_DEBUGINFO) ] || { ln -s $(LIBJVM_DTRACE_DEBUGINFO) $(LIBJVM_DTRACE_G_DEBUGINFO); } + ifeq ($(ZIP_DEBUGINFO_FILES),1) + $(ZIPEXE) -q -y $(LIBJVM_DTRACE_DIZ) $(LIBJVM_DTRACE_DEBUGINFO) $(LIBJVM_DTRACE_G_DEBUGINFO) + $(RM) $(LIBJVM_DTRACE_DEBUGINFO) $(LIBJVM_DTRACE_G_DEBUGINFO) + [ -f $(LIBJVM_DTRACE_G_DIZ) ] || { ln -s $(LIBJVM_DTRACE_DIZ) $(LIBJVM_DTRACE_G_DIZ); } + endif endif $(DTRACE).d: $(DTRACE_SRCDIR)/hotspot.d $(DTRACE_SRCDIR)/hotspot_jni.d \ diff -r e0d32945f6ab -r fa5227d43363 hotspot/make/solaris/makefiles/jsig.make --- a/hotspot/make/solaris/makefiles/jsig.make Thu May 10 20:05:12 2012 +0400 +++ b/hotspot/make/solaris/makefiles/jsig.make Thu May 10 11:47:56 2012 -0700 @@ -1,5 +1,5 @@ # -# Copyright (c) 2005, 2011, Oracle and/or its affiliates. All rights reserved. +# Copyright (c) 2005, 2012, Oracle and/or its affiliates. All rights reserved. # DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. # # This code is free software; you can redistribute it and/or modify it @@ -32,12 +32,15 @@ LIBJSIG_G = lib$(JSIG_G).so LIBJSIG_DEBUGINFO = lib$(JSIG).debuginfo +LIBJSIG_DIZ = lib$(JSIG).diz LIBJSIG_G_DEBUGINFO = lib$(JSIG_G).debuginfo +LIBJSIG_G_DIZ = lib$(JSIG_G).diz JSIGSRCDIR = $(GAMMADIR)/src/os/$(Platform_os_family)/vm DEST_JSIG = $(JDK_LIBDIR)/$(LIBJSIG) DEST_JSIG_DEBUGINFO = $(JDK_LIBDIR)/$(LIBJSIG_DEBUGINFO) +DEST_JSIG_DIZ = $(JDK_LIBDIR)/$(LIBJSIG_DIZ) LIBJSIG_MAPFILE = $(MAKEFILES_DIR)/mapfile-vers-jsig @@ -54,7 +57,7 @@ $(QUIETLY) $(CC) $(SYMFLAG) $(ARCHFLAG) $(SHARED_FLAG) $(PICFLAG) \ $(LFLAGS_JSIG) -o $@ $< -ldl [ -f $(LIBJSIG_G) ] || { ln -s $@ $(LIBJSIG_G); } -ifneq ($(OBJCOPY),) +ifeq ($(ENABLE_FULL_DEBUG_SYMBOLS),1) $(QUIETLY) $(OBJCOPY) --only-keep-debug $@ $(LIBJSIG_DEBUGINFO) $(QUIETLY) $(OBJCOPY) --add-gnu-debuglink=$(LIBJSIG_DEBUGINFO) $@ ifeq ($(STRIP_POLICY),all_strip) @@ -66,12 +69,19 @@ endif endif [ -f $(LIBJSIG_G_DEBUGINFO) ] || { ln -s $(LIBJSIG_DEBUGINFO) $(LIBJSIG_G_DEBUGINFO); } + ifeq ($(ZIP_DEBUGINFO_FILES),1) + $(ZIPEXE) -q -y $(LIBJSIG_DIZ) $(LIBJSIG_DEBUGINFO) $(LIBJSIG_G_DEBUGINFO) + $(RM) $(LIBJSIG_DEBUGINFO) $(LIBJSIG_G_DEBUGINFO) + [ -f $(LIBJSIG_G_DIZ) ] || { ln -s $(LIBJSIG_DIZ) $(LIBJSIG_G_DIZ); } + endif endif install_jsig: $(LIBJSIG) @echo "Copying $(LIBJSIG) to $(DEST_JSIG)" $(QUIETLY) test -f $(LIBJSIG_DEBUGINFO) && \ cp -f $(LIBJSIG_DEBUGINFO) $(DEST_JSIG_DEBUGINFO) + $(QUIETLY) test -f $(LIBJSIG_DIZ) && \ + cp -f $(LIBJSIG_DIZ) $(DEST_JSIG_DIZ) $(QUIETLY) cp -f $(LIBJSIG) $(DEST_JSIG) && echo "Done" .PHONY: install_jsig diff -r e0d32945f6ab -r fa5227d43363 hotspot/make/solaris/makefiles/saproc.make --- a/hotspot/make/solaris/makefiles/saproc.make Thu May 10 20:05:12 2012 +0400 +++ b/hotspot/make/solaris/makefiles/saproc.make Thu May 10 11:47:56 2012 -0700 @@ -1,5 +1,5 @@ # -# Copyright (c) 2005, 2011, Oracle and/or its affiliates. All rights reserved. +# Copyright (c) 2005, 2012, Oracle and/or its affiliates. All rights reserved. # DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. # # This code is free software; you can redistribute it and/or modify it @@ -33,7 +33,9 @@ LIBSAPROC_G = lib$(SAPROC_G).so LIBSAPROC_DEBUGINFO = lib$(SAPROC).debuginfo +LIBSAPROC_DIZ = lib$(SAPROC).diz LIBSAPROC_G_DEBUGINFO = lib$(SAPROC_G).debuginfo +LIBSAPROC_G_DIZ = lib$(SAPROC_G).diz AGENT_DIR = $(GAMMADIR)/agent @@ -45,6 +47,7 @@ DEST_SAPROC = $(JDK_LIBDIR)/$(LIBSAPROC) DEST_SAPROC_DEBUGINFO = $(JDK_LIBDIR)/$(LIBSAPROC_DEBUGINFO) +DEST_SAPROC_DIZ = $(JDK_LIBDIR)/$(LIBSAPROC_DIZ) # if $(AGENT_DIR) does not exist, we don't build SA @@ -105,7 +108,7 @@ -o $@ \ -ldl -ldemangle -lthread -lc [ -f $(LIBSAPROC_G) ] || { ln -s $@ $(LIBSAPROC_G); } -ifneq ($(OBJCOPY),) +ifeq ($(ENABLE_FULL_DEBUG_SYMBOLS),1) $(QUIETLY) $(OBJCOPY) --only-keep-debug $@ $(LIBSAPROC_DEBUGINFO) $(QUIETLY) $(OBJCOPY) --add-gnu-debuglink=$(LIBSAPROC_DEBUGINFO) $@ ifeq ($(STRIP_POLICY),all_strip) @@ -117,6 +120,11 @@ endif endif [ -f $(LIBSAPROC_G_DEBUGINFO) ] || { ln -s $(LIBSAPROC_DEBUGINFO) $(LIBSAPROC_G_DEBUGINFO); } + ifeq ($(ZIP_DEBUGINFO_FILES),1) + $(ZIPEXE) -q -y $(LIBSAPROC_DIZ) $(LIBSAPROC_DEBUGINFO) $(LIBSAPROC_G_DEBUGINFO) + $(RM) $(LIBSAPROC_DEBUGINFO) $(LIBSAPROC_G_DEBUGINFO) + [ -f $(LIBSAPROC_G_DIZ) ] || { ln -s $(LIBSAPROC_DIZ) $(LIBSAPROC_G_DIZ); } + endif endif install_saproc: $(BULDLIBSAPROC) @@ -124,6 +132,8 @@ echo "Copying $(LIBSAPROC) to $(DEST_SAPROC)"; \ test -f $(LIBSAPROC_DEBUGINFO) && \ cp -f $(LIBSAPROC_DEBUGINFO) $(DEST_SAPROC_DEBUGINFO); \ + test -f $(LIBSAPROC_DIZ) && \ + cp -f $(LIBSAPROC_DIZ) $(DEST_SAPROC_DIZ); \ cp -f $(LIBSAPROC) $(DEST_SAPROC) && echo "Done"; \ fi diff -r e0d32945f6ab -r fa5227d43363 hotspot/make/solaris/makefiles/sparcWorks.make --- a/hotspot/make/solaris/makefiles/sparcWorks.make Thu May 10 20:05:12 2012 +0400 +++ b/hotspot/make/solaris/makefiles/sparcWorks.make Thu May 10 11:47:56 2012 -0700 @@ -1,5 +1,5 @@ # -# Copyright (c) 1998, 2011, Oracle and/or its affiliates. All rights reserved. +# Copyright (c) 1998, 2012, Oracle and/or its affiliates. All rights reserved. # DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. # # This code is free software; you can redistribute it and/or modify it @@ -488,12 +488,12 @@ # The -g0 setting allows the C++ frontend to inline, which is a big win. # The -xs setting disables 'lazy debug info' which puts everything in # the .so instead of requiring the '.o' files. -ifneq ($(OBJCOPY),) +ifeq ($(ENABLE_FULL_DEBUG_SYMBOLS),1) OPT_CFLAGS += -g0 -xs endif DEBUG_CFLAGS = -g FASTDEBUG_CFLAGS = -g0 -ifneq ($(OBJCOPY),) +ifeq ($(ENABLE_FULL_DEBUG_SYMBOLS),1) DEBUG_CFLAGS += -xs FASTDEBUG_CFLAGS += -xs endif diff -r e0d32945f6ab -r fa5227d43363 hotspot/make/solaris/makefiles/vm.make --- a/hotspot/make/solaris/makefiles/vm.make Thu May 10 20:05:12 2012 +0400 +++ b/hotspot/make/solaris/makefiles/vm.make Thu May 10 11:47:56 2012 -0700 @@ -56,7 +56,7 @@ INCLUDES += $(Src_Dirs_I:%=-I%) # SYMFLAG is used by {dtrace,jsig,saproc}.make. -ifneq ($(OBJCOPY),) +ifeq ($(ENABLE_FULL_DEBUG_SYMBOLS),1) # always build with debug info when we can create .debuginfo files # and disable 'lazy debug info' so the .so has everything. SYMFLAG = -g -xs @@ -152,7 +152,9 @@ LIBJVM_G = lib$(JVM)$(G_SUFFIX).so LIBJVM_DEBUGINFO = lib$(JVM).debuginfo +LIBJVM_DIZ = lib$(JVM).diz LIBJVM_G_DEBUGINFO = lib$(JVM)$(G_SUFFIX).debuginfo +LIBJVM_G_DIZ = lib$(JVM)$(G_SUFFIX).diz SPECIAL_PATHS:=adlc c1 dist gc_implementation opto shark libadt @@ -283,7 +285,7 @@ $(QUIETLY) rm -f $@.1 && ln -s $@ $@.1 $(QUIETLY) [ -f $(LIBJVM_G) ] || ln -s $@ $(LIBJVM_G) $(QUIETLY) [ -f $(LIBJVM_G).1 ] || ln -s $@.1 $(LIBJVM_G).1 -ifneq ($(OBJCOPY),) +ifeq ($(ENABLE_FULL_DEBUG_SYMBOLS),1) $(QUIETLY) $(OBJCOPY) --only-keep-debug $@ $(LIBJVM_DEBUGINFO) $(QUIETLY) $(OBJCOPY) --add-gnu-debuglink=$(LIBJVM_DEBUGINFO) $@ ifeq ($(STRIP_POLICY),all_strip) @@ -295,6 +297,11 @@ endif endif $(QUIETLY) [ -f $(LIBJVM_G_DEBUGINFO) ] || ln -s $(LIBJVM_DEBUGINFO) $(LIBJVM_G_DEBUGINFO) + ifeq ($(ZIP_DEBUGINFO_FILES),1) + $(ZIPEXE) -q -y $(LIBJVM_DIZ) $(LIBJVM_DEBUGINFO) $(LIBJVM_G_DEBUGINFO) + $(RM) $(LIBJVM_DEBUGINFO) $(LIBJVM_G_DEBUGINFO) + [ -f $(LIBJVM_G_DIZ) ] || { ln -s $(LIBJVM_DIZ) $(LIBJVM_G_DIZ); } + endif endif endif # filter -sbfast -xsbfast @@ -302,11 +309,14 @@ DEST_SUBDIR = $(JDK_LIBDIR)/$(VM_SUBDIR) DEST_JVM = $(DEST_SUBDIR)/$(LIBJVM) DEST_JVM_DEBUGINFO = $(DEST_SUBDIR)/$(LIBJVM_DEBUGINFO) +DEST_JVM_DIZ = $(DEST_SUBDIR)/$(LIBJVM_DIZ) install_jvm: $(LIBJVM) @echo "Copying $(LIBJVM) to $(DEST_JVM)" $(QUIETLY) test -f $(LIBJVM_DEBUGINFO) && \ cp -f $(LIBJVM_DEBUGINFO) $(DEST_JVM_DEBUGINFO) + $(QUIETLY) test -f $(LIBJVM_DIZ) && \ + cp -f $(LIBJVM_DIZ) $(DEST_JVM_DIZ) $(QUIETLY) cp -f $(LIBJVM) $(DEST_JVM) && echo "Done" #---------------------------------------------------------------------- diff -r e0d32945f6ab -r fa5227d43363 hotspot/make/windows/build.make --- a/hotspot/make/windows/build.make Thu May 10 20:05:12 2012 +0400 +++ b/hotspot/make/windows/build.make Thu May 10 11:47:56 2012 -0700 @@ -1,5 +1,5 @@ # -# Copyright (c) 1998, 2011, Oracle and/or its affiliates. All rights reserved. +# Copyright (c) 1998, 2012, Oracle and/or its affiliates. All rights reserved. # DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. # # This code is free software; you can redistribute it and/or modify it @@ -302,6 +302,10 @@ @ echo MT=$(MT) >> $@ @ echo RC=$(RC) >> $@ @ sh $(WorkSpace)/make/windows/get_msc_ver.sh >> $@ + @ if "$(ENABLE_FULL_DEBUG_SYMBOLS)" NEQ "" echo ENABLE_FULL_DEBUG_SYMBOLS=$(ENABLE_FULL_DEBUG_SYMBOLS) >> $@ + @ if "$(ZIP_DEBUGINFO_FILES)" NEQ "" echo ZIP_DEBUGINFO_FILES=$(ZIP_DEBUGINFO_FILES) >> $@ + @ if "$(RM)" NEQ "" echo RM=$(RM) >> $@ + @ if "$(ZIPEXE)" NEQ "" echo ZIPEXE=$(ZIPEXE) >> $@ checks: checkVariant checkWorkSpace checkSA diff -r e0d32945f6ab -r fa5227d43363 hotspot/make/windows/makefiles/compile.make --- a/hotspot/make/windows/makefiles/compile.make Thu May 10 20:05:12 2012 +0400 +++ b/hotspot/make/windows/makefiles/compile.make Thu May 10 11:47:56 2012 -0700 @@ -1,5 +1,5 @@ # -# Copyright (c) 1997, 2011, Oracle and/or its affiliates. All rights reserved. +# Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved. # DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. # # This code is free software; you can redistribute it and/or modify it @@ -54,8 +54,10 @@ # These are always used in all compiles CXX_FLAGS=/nologo /W3 /WX -# Let's add debug information always too. +# Let's add debug information when Full Debug Symbols is enabled +!if "$(ENABLE_FULL_DEBUG_SYMBOLS)" == "1" CXX_FLAGS=$(CXX_FLAGS) /Zi +!endif # Based on BUILDARCH we add some flags and select the default compiler name !if "$(BUILDARCH)" == "ia64" @@ -239,7 +241,10 @@ LD_FLAGS= $(LD_FLAGS) kernel32.lib user32.lib gdi32.lib winspool.lib \ comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib \ uuid.lib Wsock32.lib winmm.lib /nologo /machine:$(MACHINE) /opt:REF \ - /opt:ICF,8 /map /debug + /opt:ICF,8 +!if "$(ENABLE_FULL_DEBUG_SYMBOLS)" == "1" +LD_FLAGS= $(LD_FLAGS) /map /debug +!endif !if $(MSC_VER) >= 1600 diff -r e0d32945f6ab -r fa5227d43363 hotspot/make/windows/makefiles/debug.make --- a/hotspot/make/windows/makefiles/debug.make Thu May 10 20:05:12 2012 +0400 +++ b/hotspot/make/windows/makefiles/debug.make Thu May 10 11:47:56 2012 -0700 @@ -61,6 +61,12 @@ # separately. Use ";#2" for .dll and ";#1" for .exe: $(MT) /manifest $@.manifest /outputresource:$@;#2 !endif +!if "$(ENABLE_FULL_DEBUG_SYMBOLS)" == "1" +!if "$(ZIP_DEBUGINFO_FILES)" == "1" + $(ZIPEXE) -q $*.diz $*.map $*.pdb + $(RM) $*.map $*.pdb +!endif +!endif !include $(WorkSpace)/make/windows/makefiles/shared.make !include $(WorkSpace)/make/windows/makefiles/sa.make diff -r e0d32945f6ab -r fa5227d43363 hotspot/make/windows/makefiles/defs.make --- a/hotspot/make/windows/makefiles/defs.make Thu May 10 20:05:12 2012 +0400 +++ b/hotspot/make/windows/makefiles/defs.make Thu May 10 11:47:56 2012 -0700 @@ -107,6 +107,52 @@ endif endif +# Full Debug Symbols has been enabled on Windows since JDK1.4.1 so +# there is no need for an "earlier than JDK7 check". +# The Full Debug Symbols (FDS) default for BUILD_FLAVOR == product +# builds is enabled with debug info files ZIP'ed to save space. For +# BUILD_FLAVOR != product builds, FDS is always enabled, after all a +# debug build without debug info isn't very useful. +# The ZIP_DEBUGINFO_FILES option only has meaning when FDS is enabled. +# +# If you invoke a build with FULL_DEBUG_SYMBOLS=0, then FDS will be +# disabled for a BUILD_FLAVOR == product build. +# +# Note: Use of a different variable name for the FDS override option +# versus the FDS enabled check is intentional (FULL_DEBUG_SYMBOLS +# versus ENABLE_FULL_DEBUG_SYMBOLS). For auto build systems that pass +# in options via environment variables, use of distinct variables +# prevents strange behaviours. For example, in a BUILD_FLAVOR != +# product build, the FULL_DEBUG_SYMBOLS environment variable will be +# 0, but the ENABLE_FULL_DEBUG_SYMBOLS make variable will be 1. If +# the same variable name is used, then different values can be picked +# up by different parts of the build. Just to be clear, we only need +# two variable names because the incoming option value can be +# overridden in some situations, e.g., a BUILD_FLAVOR != product +# build. + +ifeq ($(BUILD_FLAVOR), product) + FULL_DEBUG_SYMBOLS ?= 1 + ENABLE_FULL_DEBUG_SYMBOLS = $(FULL_DEBUG_SYMBOLS) +else + # debug variants always get Full Debug Symbols (if available) + ENABLE_FULL_DEBUG_SYMBOLS = 1 +endif +_JUNK_ := $(shell \ + echo >&2 "INFO: ENABLE_FULL_DEBUG_SYMBOLS=$(ENABLE_FULL_DEBUG_SYMBOLS)") +MAKE_ARGS += ENABLE_FULL_DEBUG_SYMBOLS=$(ENABLE_FULL_DEBUG_SYMBOLS) + +ifeq ($(ENABLE_FULL_DEBUG_SYMBOLS),1) + # Disable ZIP_DEBUGINFO_FILES by default because various tests are + # failing in nightly when the debug info files are ZIP'ed. + ZIP_DEBUGINFO_FILES ?= 0 +else + ZIP_DEBUGINFO_FILES=0 +endif +MAKE_ARGS += ZIP_DEBUGINFO_FILES=$(ZIP_DEBUGINFO_FILES) +MAKE_ARGS += RM="$(RM)" +MAKE_ARGS += ZIPEXE=$(ZIPEXE) + # On 32 bit windows we build server, client and kernel, on 64 bit just server. ifeq ($(JVM_VARIANTS),) ifeq ($(ARCH_DATA_MODEL), 32) @@ -193,29 +239,53 @@ ifeq ($(JVM_VARIANT_SERVER),true) EXPORT_LIST += $(EXPORT_SERVER_DIR)/Xusage.txt EXPORT_LIST += $(EXPORT_SERVER_DIR)/jvm.$(LIBRARY_SUFFIX) - EXPORT_LIST += $(EXPORT_SERVER_DIR)/jvm.pdb - EXPORT_LIST += $(EXPORT_SERVER_DIR)/jvm.map + ifeq ($(ENABLE_FULL_DEBUG_SYMBOLS),1) + ifeq ($(ZIP_DEBUGINFO_FILES),1) + EXPORT_LIST += $(EXPORT_SERVER_DIR)/jvm.diz + else + EXPORT_LIST += $(EXPORT_SERVER_DIR)/jvm.pdb + EXPORT_LIST += $(EXPORT_SERVER_DIR)/jvm.map + endif + endif EXPORT_LIST += $(EXPORT_LIB_DIR)/jvm.lib endif ifeq ($(JVM_VARIANT_CLIENT),true) EXPORT_LIST += $(EXPORT_CLIENT_DIR)/Xusage.txt EXPORT_LIST += $(EXPORT_CLIENT_DIR)/jvm.$(LIBRARY_SUFFIX) - EXPORT_LIST += $(EXPORT_CLIENT_DIR)/jvm.pdb - EXPORT_LIST += $(EXPORT_CLIENT_DIR)/jvm.map + ifeq ($(ENABLE_FULL_DEBUG_SYMBOLS),1) + ifeq ($(ZIP_DEBUGINFO_FILES),1) + EXPORT_LIST += $(EXPORT_CLIENT_DIR)/jvm.diz + else + EXPORT_LIST += $(EXPORT_CLIENT_DIR)/jvm.pdb + EXPORT_LIST += $(EXPORT_CLIENT_DIR)/jvm.map + endif + endif endif ifeq ($(JVM_VARIANT_KERNEL),true) EXPORT_LIST += $(EXPORT_KERNEL_DIR)/Xusage.txt EXPORT_LIST += $(EXPORT_KERNEL_DIR)/jvm.$(LIBRARY_SUFFIX) - EXPORT_LIST += $(EXPORT_KERNEL_DIR)/jvm.pdb - EXPORT_LIST += $(EXPORT_KERNEL_DIR)/jvm.map + ifeq ($(ENABLE_FULL_DEBUG_SYMBOLS),1) + ifeq ($(ZIP_DEBUGINFO_FILES),1) + EXPORT_LIST += $(EXPORT_KERNEL_DIR)/jvm.diz + else + EXPORT_LIST += $(EXPORT_KERNEL_DIR)/jvm.pdb + EXPORT_LIST += $(EXPORT_KERNEL_DIR)/jvm.map + endif + endif endif EXPORT_LIST += $(EXPORT_JRE_LIB_DIR)/wb.jar ifeq ($(BUILD_WIN_SA), 1) EXPORT_LIST += $(EXPORT_JRE_BIN_DIR)/sawindbg.$(LIBRARY_SUFFIX) - EXPORT_LIST += $(EXPORT_JRE_BIN_DIR)/sawindbg.pdb - EXPORT_LIST += $(EXPORT_JRE_BIN_DIR)/sawindbg.map + ifeq ($(ENABLE_FULL_DEBUG_SYMBOLS),1) + ifeq ($(ZIP_DEBUGINFO_FILES),1) + EXPORT_LIST += $(EXPORT_JRE_BIN_DIR)/sawindbg.diz + else + EXPORT_LIST += $(EXPORT_JRE_BIN_DIR)/sawindbg.pdb + EXPORT_LIST += $(EXPORT_JRE_BIN_DIR)/sawindbg.map + endif + endif EXPORT_LIST += $(EXPORT_LIB_DIR)/sa-jdi.jar # Must pass this down to nmake. MAKE_ARGS += BUILD_WIN_SA=1 diff -r e0d32945f6ab -r fa5227d43363 hotspot/make/windows/makefiles/fastdebug.make --- a/hotspot/make/windows/makefiles/fastdebug.make Thu May 10 20:05:12 2012 +0400 +++ b/hotspot/make/windows/makefiles/fastdebug.make Thu May 10 11:47:56 2012 -0700 @@ -61,6 +61,12 @@ # separately. Use ";#2" for .dll and ";#1" for .exe: $(MT) /manifest $@.manifest /outputresource:$@;#2 !endif +!if "$(ENABLE_FULL_DEBUG_SYMBOLS)" == "1" +!if "$(ZIP_DEBUGINFO_FILES)" == "1" + $(ZIPEXE) -q $*.diz $*.map $*.pdb + $(RM) $*.map $*.pdb +!endif +!endif !include $(WorkSpace)/make/windows/makefiles/shared.make !include $(WorkSpace)/make/windows/makefiles/sa.make diff -r e0d32945f6ab -r fa5227d43363 hotspot/make/windows/makefiles/product.make --- a/hotspot/make/windows/makefiles/product.make Thu May 10 20:05:12 2012 +0400 +++ b/hotspot/make/windows/makefiles/product.make Thu May 10 11:47:56 2012 -0700 @@ -72,6 +72,12 @@ # separately. Use ";#2" for .dll and ";#1" for .exe: $(MT) /manifest $@.manifest /outputresource:$@;#2 !endif +!if "$(ENABLE_FULL_DEBUG_SYMBOLS)" == "1" +!if "$(ZIP_DEBUGINFO_FILES)" == "1" + $(ZIPEXE) -q $*.diz $*.map $*.pdb + $(RM) $*.map $*.pdb +!endif +!endif !include $(WorkSpace)/make/windows/makefiles/shared.make !include $(WorkSpace)/make/windows/makefiles/sa.make diff -r e0d32945f6ab -r fa5227d43363 hotspot/make/windows/makefiles/sa.make --- a/hotspot/make/windows/makefiles/sa.make Thu May 10 20:05:12 2012 +0400 +++ b/hotspot/make/windows/makefiles/sa.make Thu May 10 11:47:56 2012 -0700 @@ -1,5 +1,5 @@ # -# Copyright (c) 2003, 2011, Oracle and/or its affiliates. All rights reserved. +# Copyright (c) 2003, 2012, Oracle and/or its affiliates. All rights reserved. # DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. # # This code is free software; you can redistribute it and/or modify it @@ -94,13 +94,19 @@ SA_LD_FLAGS = bufferoverflowU.lib !endif !else -SA_CFLAGS = /nologo $(MS_RUNTIME_OPTION) /W3 /Gm $(GX_OPTION) /ZI /Od /D "WIN32" /D "_WINDOWS" /D "_DEBUG" /D "_CONSOLE" /D "_MBCS" /YX /FD /GZ /c +SA_CFLAGS = /nologo $(MS_RUNTIME_OPTION) /W3 /Gm $(GX_OPTION) /Od /D "WIN32" /D "_WINDOWS" /D "_DEBUG" /D "_CONSOLE" /D "_MBCS" /YX /FD /GZ /c +!if "$(ENABLE_FULL_DEBUG_SYMBOLS)" == "1" +SA_CFLAGS = $(SA_CFLAGS) /ZI +!endif !endif !if "$(MT)" != "" SA_LD_FLAGS = /manifest $(SA_LD_FLAGS) !endif SASRCFILE = $(AGENT_DIR)/src/os/win32/windbg/sawindbg.cpp -SA_LFLAGS = $(SA_LD_FLAGS) /nologo /subsystem:console /map /debug /machine:$(MACHINE) +SA_LFLAGS = $(SA_LD_FLAGS) /nologo /subsystem:console /machine:$(MACHINE) +!if "$(ENABLE_FULL_DEBUG_SYMBOLS)" == "1" +SA_LFLAGS = $(SA_LFLAGS) /map /debug +!endif # Note that we do not keep sawindbj.obj around as it would then # get included in the dumpbin command in build_vm_def.sh @@ -114,14 +120,20 @@ /I"$(BootStrapDir)/include" /I"$(BootStrapDir)/include/win32" /I"$(GENERATED)" $(SA_CFLAGS) $(SASRCFILE) - /out:sawindbg.obj + /out:$*.obj << set LIB=$(SA_LIB)$(LIB) - $(LD) /out:$@ /DLL sawindbg.obj dbgeng.lib $(SA_LFLAGS) + $(LD) /out:$@ /DLL $*.obj dbgeng.lib $(SA_LFLAGS) !if "$(MT)" != "" $(MT) /manifest $(@F).manifest /outputresource:$(@F);#2 !endif - -@rm -f sawindbg.obj +!if "$(ENABLE_FULL_DEBUG_SYMBOLS)" == "1" +!if "$(ZIP_DEBUGINFO_FILES)" == "1" + $(ZIPEXE) -q $*.diz $*.map $*.pdb + $(RM) $*.map $*.pdb +!endif +!endif + -@rm -f $*.obj cleanall : rm -rf $(GENERATED:\=/)/saclasses diff -r e0d32945f6ab -r fa5227d43363 hotspot/src/os/solaris/vm/attachListener_solaris.cpp --- a/hotspot/src/os/solaris/vm/attachListener_solaris.cpp Thu May 10 20:05:12 2012 +0400 +++ b/hotspot/src/os/solaris/vm/attachListener_solaris.cpp Thu May 10 11:47:56 2012 -0700 @@ -336,7 +336,9 @@ // Return 0 (success) + file descriptor, or non-0 (error) if (res == 0) { door_desc_t desc; - desc.d_attributes = DOOR_DESCRIPTOR; + // DOOR_RELEASE flag makes sure fd is closed after passing it to + // the client. See door_return(3DOOR) man page. + desc.d_attributes = DOOR_DESCRIPTOR | DOOR_RELEASE; desc.d_data.d_desc.d_descriptor = return_fd; door_return((char*)&res, sizeof(res), &desc, 1); } else { diff -r e0d32945f6ab -r fa5227d43363 hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/binaryTreeDictionary.cpp --- a/hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/binaryTreeDictionary.cpp Thu May 10 20:05:12 2012 +0400 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,1257 +0,0 @@ -/* - * Copyright (c) 2001, 2010, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - * - */ - -#include "precompiled.hpp" -#include "gc_implementation/concurrentMarkSweep/binaryTreeDictionary.hpp" -#include "gc_implementation/shared/allocationStats.hpp" -#include "gc_implementation/shared/spaceDecorator.hpp" -#include "memory/space.inline.hpp" -#include "runtime/globals.hpp" -#include "utilities/ostream.hpp" - -//////////////////////////////////////////////////////////////////////////////// -// A binary tree based search structure for free blocks. -// This is currently used in the Concurrent Mark&Sweep implementation. -//////////////////////////////////////////////////////////////////////////////// - -TreeChunk* TreeChunk::as_TreeChunk(FreeChunk* fc) { - // Do some assertion checking here. - return (TreeChunk*) fc; -} - -void TreeChunk::verifyTreeChunkList() const { - TreeChunk* nextTC = (TreeChunk*)next(); - if (prev() != NULL) { // interior list node shouldn'r have tree fields - guarantee(embedded_list()->parent() == NULL && embedded_list()->left() == NULL && - embedded_list()->right() == NULL, "should be clear"); - } - if (nextTC != NULL) { - guarantee(as_TreeChunk(nextTC->prev()) == this, "broken chain"); - guarantee(nextTC->size() == size(), "wrong size"); - nextTC->verifyTreeChunkList(); - } -} - - -TreeList* TreeList::as_TreeList(TreeChunk* tc) { - // This first free chunk in the list will be the tree list. - assert(tc->size() >= sizeof(TreeChunk), "Chunk is too small for a TreeChunk"); - TreeList* tl = tc->embedded_list(); - tc->set_list(tl); -#ifdef ASSERT - tl->set_protecting_lock(NULL); -#endif - tl->set_hint(0); - tl->set_size(tc->size()); - tl->link_head(tc); - tl->link_tail(tc); - tl->set_count(1); - tl->init_statistics(true /* split_birth */); - tl->setParent(NULL); - tl->setLeft(NULL); - tl->setRight(NULL); - return tl; -} - -TreeList* TreeList::as_TreeList(HeapWord* addr, size_t size) { - TreeChunk* tc = (TreeChunk*) addr; - assert(size >= sizeof(TreeChunk), "Chunk is too small for a TreeChunk"); - // The space in the heap will have been mangled initially but - // is not remangled when a free chunk is returned to the free list - // (since it is used to maintain the chunk on the free list). - assert((ZapUnusedHeapArea && - SpaceMangler::is_mangled((HeapWord*) tc->size_addr()) && - SpaceMangler::is_mangled((HeapWord*) tc->prev_addr()) && - SpaceMangler::is_mangled((HeapWord*) tc->next_addr())) || - (tc->size() == 0 && tc->prev() == NULL && tc->next() == NULL), - "Space should be clear or mangled"); - tc->setSize(size); - tc->linkPrev(NULL); - tc->linkNext(NULL); - TreeList* tl = TreeList::as_TreeList(tc); - return tl; -} - -TreeList* TreeList::removeChunkReplaceIfNeeded(TreeChunk* tc) { - - TreeList* retTL = this; - FreeChunk* list = head(); - assert(!list || list != list->next(), "Chunk on list twice"); - assert(tc != NULL, "Chunk being removed is NULL"); - assert(parent() == NULL || this == parent()->left() || - this == parent()->right(), "list is inconsistent"); - assert(tc->isFree(), "Header is not marked correctly"); - assert(head() == NULL || head()->prev() == NULL, "list invariant"); - assert(tail() == NULL || tail()->next() == NULL, "list invariant"); - - FreeChunk* prevFC = tc->prev(); - TreeChunk* nextTC = TreeChunk::as_TreeChunk(tc->next()); - assert(list != NULL, "should have at least the target chunk"); - - // Is this the first item on the list? - if (tc == list) { - // The "getChunk..." functions for a TreeList will not return the - // first chunk in the list unless it is the last chunk in the list - // because the first chunk is also acting as the tree node. - // When coalescing happens, however, the first chunk in the a tree - // list can be the start of a free range. Free ranges are removed - // from the free lists so that they are not available to be - // allocated when the sweeper yields (giving up the free list lock) - // to allow mutator activity. If this chunk is the first in the - // list and is not the last in the list, do the work to copy the - // TreeList from the first chunk to the next chunk and update all - // the TreeList pointers in the chunks in the list. - if (nextTC == NULL) { - assert(prevFC == NULL, "Not last chunk in the list"); - set_tail(NULL); - set_head(NULL); - } else { - // copy embedded list. - nextTC->set_embedded_list(tc->embedded_list()); - retTL = nextTC->embedded_list(); - // Fix the pointer to the list in each chunk in the list. - // This can be slow for a long list. Consider having - // an option that does not allow the first chunk on the - // list to be coalesced. - for (TreeChunk* curTC = nextTC; curTC != NULL; - curTC = TreeChunk::as_TreeChunk(curTC->next())) { - curTC->set_list(retTL); - } - // Fix the parent to point to the new TreeList. - if (retTL->parent() != NULL) { - if (this == retTL->parent()->left()) { - retTL->parent()->setLeft(retTL); - } else { - assert(this == retTL->parent()->right(), "Parent is incorrect"); - retTL->parent()->setRight(retTL); - } - } - // Fix the children's parent pointers to point to the - // new list. - assert(right() == retTL->right(), "Should have been copied"); - if (retTL->right() != NULL) { - retTL->right()->setParent(retTL); - } - assert(left() == retTL->left(), "Should have been copied"); - if (retTL->left() != NULL) { - retTL->left()->setParent(retTL); - } - retTL->link_head(nextTC); - assert(nextTC->isFree(), "Should be a free chunk"); - } - } else { - if (nextTC == NULL) { - // Removing chunk at tail of list - link_tail(prevFC); - } - // Chunk is interior to the list - prevFC->linkAfter(nextTC); - } - - // Below this point the embeded TreeList being used for the - // tree node may have changed. Don't use "this" - // TreeList*. - // chunk should still be a free chunk (bit set in _prev) - assert(!retTL->head() || retTL->size() == retTL->head()->size(), - "Wrong sized chunk in list"); - debug_only( - tc->linkPrev(NULL); - tc->linkNext(NULL); - tc->set_list(NULL); - bool prev_found = false; - bool next_found = false; - for (FreeChunk* curFC = retTL->head(); - curFC != NULL; curFC = curFC->next()) { - assert(curFC != tc, "Chunk is still in list"); - if (curFC == prevFC) { - prev_found = true; - } - if (curFC == nextTC) { - next_found = true; - } - } - assert(prevFC == NULL || prev_found, "Chunk was lost from list"); - assert(nextTC == NULL || next_found, "Chunk was lost from list"); - assert(retTL->parent() == NULL || - retTL == retTL->parent()->left() || - retTL == retTL->parent()->right(), - "list is inconsistent"); - ) - retTL->decrement_count(); - - assert(tc->isFree(), "Should still be a free chunk"); - assert(retTL->head() == NULL || retTL->head()->prev() == NULL, - "list invariant"); - assert(retTL->tail() == NULL || retTL->tail()->next() == NULL, - "list invariant"); - return retTL; -} -void TreeList::returnChunkAtTail(TreeChunk* chunk) { - assert(chunk != NULL, "returning NULL chunk"); - assert(chunk->list() == this, "list should be set for chunk"); - assert(tail() != NULL, "The tree list is embedded in the first chunk"); - // which means that the list can never be empty. - assert(!verifyChunkInFreeLists(chunk), "Double entry"); - assert(head() == NULL || head()->prev() == NULL, "list invariant"); - assert(tail() == NULL || tail()->next() == NULL, "list invariant"); - - FreeChunk* fc = tail(); - fc->linkAfter(chunk); - link_tail(chunk); - - assert(!tail() || size() == tail()->size(), "Wrong sized chunk in list"); - increment_count(); - debug_only(increment_returnedBytes_by(chunk->size()*sizeof(HeapWord));) - assert(head() == NULL || head()->prev() == NULL, "list invariant"); - assert(tail() == NULL || tail()->next() == NULL, "list invariant"); -} - -// Add this chunk at the head of the list. "At the head of the list" -// is defined to be after the chunk pointer to by head(). This is -// because the TreeList is embedded in the first TreeChunk in the -// list. See the definition of TreeChunk. -void TreeList::returnChunkAtHead(TreeChunk* chunk) { - assert(chunk->list() == this, "list should be set for chunk"); - assert(head() != NULL, "The tree list is embedded in the first chunk"); - assert(chunk != NULL, "returning NULL chunk"); - assert(!verifyChunkInFreeLists(chunk), "Double entry"); - assert(head() == NULL || head()->prev() == NULL, "list invariant"); - assert(tail() == NULL || tail()->next() == NULL, "list invariant"); - - FreeChunk* fc = head()->next(); - if (fc != NULL) { - chunk->linkAfter(fc); - } else { - assert(tail() == NULL, "List is inconsistent"); - link_tail(chunk); - } - head()->linkAfter(chunk); - assert(!head() || size() == head()->size(), "Wrong sized chunk in list"); - increment_count(); - debug_only(increment_returnedBytes_by(chunk->size()*sizeof(HeapWord));) - assert(head() == NULL || head()->prev() == NULL, "list invariant"); - assert(tail() == NULL || tail()->next() == NULL, "list invariant"); -} - -TreeChunk* TreeList::head_as_TreeChunk() { - assert(head() == NULL || TreeChunk::as_TreeChunk(head())->list() == this, - "Wrong type of chunk?"); - return TreeChunk::as_TreeChunk(head()); -} - -TreeChunk* TreeList::first_available() { - assert(head() != NULL, "The head of the list cannot be NULL"); - FreeChunk* fc = head()->next(); - TreeChunk* retTC; - if (fc == NULL) { - retTC = head_as_TreeChunk(); - } else { - retTC = TreeChunk::as_TreeChunk(fc); - } - assert(retTC->list() == this, "Wrong type of chunk."); - return retTC; -} - -// Returns the block with the largest heap address amongst -// those in the list for this size; potentially slow and expensive, -// use with caution! -TreeChunk* TreeList::largest_address() { - assert(head() != NULL, "The head of the list cannot be NULL"); - FreeChunk* fc = head()->next(); - TreeChunk* retTC; - if (fc == NULL) { - retTC = head_as_TreeChunk(); - } else { - // walk down the list and return the one with the highest - // heap address among chunks of this size. - FreeChunk* last = fc; - while (fc->next() != NULL) { - if ((HeapWord*)last < (HeapWord*)fc) { - last = fc; - } - fc = fc->next(); - } - retTC = TreeChunk::as_TreeChunk(last); - } - assert(retTC->list() == this, "Wrong type of chunk."); - return retTC; -} - -BinaryTreeDictionary::BinaryTreeDictionary(MemRegion mr, bool splay): - _splay(splay) -{ - assert(mr.byte_size() > MIN_TREE_CHUNK_SIZE, "minimum chunk size"); - - reset(mr); - assert(root()->left() == NULL, "reset check failed"); - assert(root()->right() == NULL, "reset check failed"); - assert(root()->head()->next() == NULL, "reset check failed"); - assert(root()->head()->prev() == NULL, "reset check failed"); - assert(totalSize() == root()->size(), "reset check failed"); - assert(totalFreeBlocks() == 1, "reset check failed"); -} - -void BinaryTreeDictionary::inc_totalSize(size_t inc) { - _totalSize = _totalSize + inc; -} - -void BinaryTreeDictionary::dec_totalSize(size_t dec) { - _totalSize = _totalSize - dec; -} - -void BinaryTreeDictionary::reset(MemRegion mr) { - assert(mr.byte_size() > MIN_TREE_CHUNK_SIZE, "minimum chunk size"); - set_root(TreeList::as_TreeList(mr.start(), mr.word_size())); - set_totalSize(mr.word_size()); - set_totalFreeBlocks(1); -} - -void BinaryTreeDictionary::reset(HeapWord* addr, size_t byte_size) { - MemRegion mr(addr, heap_word_size(byte_size)); - reset(mr); -} - -void BinaryTreeDictionary::reset() { - set_root(NULL); - set_totalSize(0); - set_totalFreeBlocks(0); -} - -// Get a free block of size at least size from tree, or NULL. -// If a splay step is requested, the removal algorithm (only) incorporates -// a splay step as follows: -// . the search proceeds down the tree looking for a possible -// match. At the (closest) matching location, an appropriate splay step is applied -// (zig, zig-zig or zig-zag). A chunk of the appropriate size is then returned -// if available, and if it's the last chunk, the node is deleted. A deteleted -// node is replaced in place by its tree successor. -TreeChunk* -BinaryTreeDictionary::getChunkFromTree(size_t size, Dither dither, bool splay) -{ - TreeList *curTL, *prevTL; - TreeChunk* retTC = NULL; - assert(size >= MIN_TREE_CHUNK_SIZE, "minimum chunk size"); - if (FLSVerifyDictionary) { - verifyTree(); - } - // starting at the root, work downwards trying to find match. - // Remember the last node of size too great or too small. - for (prevTL = curTL = root(); curTL != NULL;) { - if (curTL->size() == size) { // exact match - break; - } - prevTL = curTL; - if (curTL->size() < size) { // proceed to right sub-tree - curTL = curTL->right(); - } else { // proceed to left sub-tree - assert(curTL->size() > size, "size inconsistency"); - curTL = curTL->left(); - } - } - if (curTL == NULL) { // couldn't find exact match - // try and find the next larger size by walking back up the search path - for (curTL = prevTL; curTL != NULL;) { - if (curTL->size() >= size) break; - else curTL = curTL->parent(); - } - assert(curTL == NULL || curTL->count() > 0, - "An empty list should not be in the tree"); - } - if (curTL != NULL) { - assert(curTL->size() >= size, "size inconsistency"); - if (UseCMSAdaptiveFreeLists) { - - // A candidate chunk has been found. If it is already under - // populated, get a chunk associated with the hint for this - // chunk. - if (curTL->surplus() <= 0) { - /* Use the hint to find a size with a surplus, and reset the hint. */ - TreeList* hintTL = curTL; - while (hintTL->hint() != 0) { - assert(hintTL->hint() == 0 || hintTL->hint() > hintTL->size(), - "hint points in the wrong direction"); - hintTL = findList(hintTL->hint()); - assert(curTL != hintTL, "Infinite loop"); - if (hintTL == NULL || - hintTL == curTL /* Should not happen but protect against it */ ) { - // No useful hint. Set the hint to NULL and go on. - curTL->set_hint(0); - break; - } - assert(hintTL->size() > size, "hint is inconsistent"); - if (hintTL->surplus() > 0) { - // The hint led to a list that has a surplus. Use it. - // Set the hint for the candidate to an overpopulated - // size. - curTL->set_hint(hintTL->size()); - // Change the candidate. - curTL = hintTL; - break; - } - // The evm code reset the hint of the candidate as - // at an interim point. Why? Seems like this leaves - // the hint pointing to a list that didn't work. - // curTL->set_hint(hintTL->size()); - } - } - } - // don't waste time splaying if chunk's singleton - if (splay && curTL->head()->next() != NULL) { - semiSplayStep(curTL); - } - retTC = curTL->first_available(); - assert((retTC != NULL) && (curTL->count() > 0), - "A list in the binary tree should not be NULL"); - assert(retTC->size() >= size, - "A chunk of the wrong size was found"); - removeChunkFromTree(retTC); - assert(retTC->isFree(), "Header is not marked correctly"); - } - - if (FLSVerifyDictionary) { - verify(); - } - return retTC; -} - -TreeList* BinaryTreeDictionary::findList(size_t size) const { - TreeList* curTL; - for (curTL = root(); curTL != NULL;) { - if (curTL->size() == size) { // exact match - break; - } - - if (curTL->size() < size) { // proceed to right sub-tree - curTL = curTL->right(); - } else { // proceed to left sub-tree - assert(curTL->size() > size, "size inconsistency"); - curTL = curTL->left(); - } - } - return curTL; -} - - -bool BinaryTreeDictionary::verifyChunkInFreeLists(FreeChunk* tc) const { - size_t size = tc->size(); - TreeList* tl = findList(size); - if (tl == NULL) { - return false; - } else { - return tl->verifyChunkInFreeLists(tc); - } -} - -FreeChunk* BinaryTreeDictionary::findLargestDict() const { - TreeList *curTL = root(); - if (curTL != NULL) { - while(curTL->right() != NULL) curTL = curTL->right(); - return curTL->largest_address(); - } else { - return NULL; - } -} - -// Remove the current chunk from the tree. If it is not the last -// chunk in a list on a tree node, just unlink it. -// If it is the last chunk in the list (the next link is NULL), -// remove the node and repair the tree. -TreeChunk* -BinaryTreeDictionary::removeChunkFromTree(TreeChunk* tc) { - assert(tc != NULL, "Should not call with a NULL chunk"); - assert(tc->isFree(), "Header is not marked correctly"); - - TreeList *newTL, *parentTL; - TreeChunk* retTC; - TreeList* tl = tc->list(); - debug_only( - bool removing_only_chunk = false; - if (tl == _root) { - if ((_root->left() == NULL) && (_root->right() == NULL)) { - if (_root->count() == 1) { - assert(_root->head() == tc, "Should only be this one chunk"); - removing_only_chunk = true; - } - } - } - ) - assert(tl != NULL, "List should be set"); - assert(tl->parent() == NULL || tl == tl->parent()->left() || - tl == tl->parent()->right(), "list is inconsistent"); - - bool complicatedSplice = false; - - retTC = tc; - // Removing this chunk can have the side effect of changing the node - // (TreeList*) in the tree. If the node is the root, update it. - TreeList* replacementTL = tl->removeChunkReplaceIfNeeded(tc); - assert(tc->isFree(), "Chunk should still be free"); - assert(replacementTL->parent() == NULL || - replacementTL == replacementTL->parent()->left() || - replacementTL == replacementTL->parent()->right(), - "list is inconsistent"); - if (tl == root()) { - assert(replacementTL->parent() == NULL, "Incorrectly replacing root"); - set_root(replacementTL); - } - debug_only( - if (tl != replacementTL) { - assert(replacementTL->head() != NULL, - "If the tree list was replaced, it should not be a NULL list"); - TreeList* rhl = replacementTL->head_as_TreeChunk()->list(); - TreeList* rtl = TreeChunk::as_TreeChunk(replacementTL->tail())->list(); - assert(rhl == replacementTL, "Broken head"); - assert(rtl == replacementTL, "Broken tail"); - assert(replacementTL->size() == tc->size(), "Broken size"); - } - ) - - // Does the tree need to be repaired? - if (replacementTL->count() == 0) { - assert(replacementTL->head() == NULL && - replacementTL->tail() == NULL, "list count is incorrect"); - // Find the replacement node for the (soon to be empty) node being removed. - // if we have a single (or no) child, splice child in our stead - if (replacementTL->left() == NULL) { - // left is NULL so pick right. right may also be NULL. - newTL = replacementTL->right(); - debug_only(replacementTL->clearRight();) - } else if (replacementTL->right() == NULL) { - // right is NULL - newTL = replacementTL->left(); - debug_only(replacementTL->clearLeft();) - } else { // we have both children, so, by patriarchal convention, - // my replacement is least node in right sub-tree - complicatedSplice = true; - newTL = removeTreeMinimum(replacementTL->right()); - assert(newTL != NULL && newTL->left() == NULL && - newTL->right() == NULL, "sub-tree minimum exists"); - } - // newTL is the replacement for the (soon to be empty) node. - // newTL may be NULL. - // should verify; we just cleanly excised our replacement - if (FLSVerifyDictionary) { - verifyTree(); - } - // first make newTL my parent's child - if ((parentTL = replacementTL->parent()) == NULL) { - // newTL should be root - assert(tl == root(), "Incorrectly replacing root"); - set_root(newTL); - if (newTL != NULL) { - newTL->clearParent(); - } - } else if (parentTL->right() == replacementTL) { - // replacementTL is a right child - parentTL->setRight(newTL); - } else { // replacementTL is a left child - assert(parentTL->left() == replacementTL, "should be left child"); - parentTL->setLeft(newTL); - } - debug_only(replacementTL->clearParent();) - if (complicatedSplice) { // we need newTL to get replacementTL's - // two children - assert(newTL != NULL && - newTL->left() == NULL && newTL->right() == NULL, - "newTL should not have encumbrances from the past"); - // we'd like to assert as below: - // assert(replacementTL->left() != NULL && replacementTL->right() != NULL, - // "else !complicatedSplice"); - // ... however, the above assertion is too strong because we aren't - // guaranteed that replacementTL->right() is still NULL. - // Recall that we removed - // the right sub-tree minimum from replacementTL. - // That may well have been its right - // child! So we'll just assert half of the above: - assert(replacementTL->left() != NULL, "else !complicatedSplice"); - newTL->setLeft(replacementTL->left()); - newTL->setRight(replacementTL->right()); - debug_only( - replacementTL->clearRight(); - replacementTL->clearLeft(); - ) - } - assert(replacementTL->right() == NULL && - replacementTL->left() == NULL && - replacementTL->parent() == NULL, - "delete without encumbrances"); - } - - assert(totalSize() >= retTC->size(), "Incorrect total size"); - dec_totalSize(retTC->size()); // size book-keeping - assert(totalFreeBlocks() > 0, "Incorrect total count"); - set_totalFreeBlocks(totalFreeBlocks() - 1); - - assert(retTC != NULL, "null chunk?"); - assert(retTC->prev() == NULL && retTC->next() == NULL, - "should return without encumbrances"); - if (FLSVerifyDictionary) { - verifyTree(); - } - assert(!removing_only_chunk || _root == NULL, "root should be NULL"); - return TreeChunk::as_TreeChunk(retTC); -} - -// Remove the leftmost node (lm) in the tree and return it. -// If lm has a right child, link it to the left node of -// the parent of lm. -TreeList* BinaryTreeDictionary::removeTreeMinimum(TreeList* tl) { - assert(tl != NULL && tl->parent() != NULL, "really need a proper sub-tree"); - // locate the subtree minimum by walking down left branches - TreeList* curTL = tl; - for (; curTL->left() != NULL; curTL = curTL->left()); - // obviously curTL now has at most one child, a right child - if (curTL != root()) { // Should this test just be removed? - TreeList* parentTL = curTL->parent(); - if (parentTL->left() == curTL) { // curTL is a left child - parentTL->setLeft(curTL->right()); - } else { - // If the list tl has no left child, then curTL may be - // the right child of parentTL. - assert(parentTL->right() == curTL, "should be a right child"); - parentTL->setRight(curTL->right()); - } - } else { - // The only use of this method would not pass the root of the - // tree (as indicated by the assertion above that the tree list - // has a parent) but the specification does not explicitly exclude the - // passing of the root so accomodate it. - set_root(NULL); - } - debug_only( - curTL->clearParent(); // Test if this needs to be cleared - curTL->clearRight(); // recall, above, left child is already null - ) - // we just excised a (non-root) node, we should still verify all tree invariants - if (FLSVerifyDictionary) { - verifyTree(); - } - return curTL; -} - -// Based on a simplification of the algorithm by Sleator and Tarjan (JACM 1985). -// The simplifications are the following: -// . we splay only when we delete (not when we insert) -// . we apply a single spay step per deletion/access -// By doing such partial splaying, we reduce the amount of restructuring, -// while getting a reasonably efficient search tree (we think). -// [Measurements will be needed to (in)validate this expectation.] - -void BinaryTreeDictionary::semiSplayStep(TreeList* tc) { - // apply a semi-splay step at the given node: - // . if root, norting needs to be done - // . if child of root, splay once - // . else zig-zig or sig-zag depending on path from grandparent - if (root() == tc) return; - warning("*** Splaying not yet implemented; " - "tree operations may be inefficient ***"); -} - -void BinaryTreeDictionary::insertChunkInTree(FreeChunk* fc) { - TreeList *curTL, *prevTL; - size_t size = fc->size(); - - assert(size >= MIN_TREE_CHUNK_SIZE, "too small to be a TreeList"); - if (FLSVerifyDictionary) { - verifyTree(); - } - // XXX: do i need to clear the FreeChunk fields, let me do it just in case - // Revisit this later - - fc->clearNext(); - fc->linkPrev(NULL); - - // work down from the _root, looking for insertion point - for (prevTL = curTL = root(); curTL != NULL;) { - if (curTL->size() == size) // exact match - break; - prevTL = curTL; - if (curTL->size() > size) { // follow left branch - curTL = curTL->left(); - } else { // follow right branch - assert(curTL->size() < size, "size inconsistency"); - curTL = curTL->right(); - } - } - TreeChunk* tc = TreeChunk::as_TreeChunk(fc); - // This chunk is being returned to the binary tree. Its embedded - // TreeList should be unused at this point. - tc->initialize(); - if (curTL != NULL) { // exact match - tc->set_list(curTL); - curTL->returnChunkAtTail(tc); - } else { // need a new node in tree - tc->clearNext(); - tc->linkPrev(NULL); - TreeList* newTL = TreeList::as_TreeList(tc); - assert(((TreeChunk*)tc)->list() == newTL, - "List was not initialized correctly"); - if (prevTL == NULL) { // we are the only tree node - assert(root() == NULL, "control point invariant"); - set_root(newTL); - } else { // insert under prevTL ... - if (prevTL->size() < size) { // am right child - assert(prevTL->right() == NULL, "control point invariant"); - prevTL->setRight(newTL); - } else { // am left child - assert(prevTL->size() > size && prevTL->left() == NULL, "cpt pt inv"); - prevTL->setLeft(newTL); - } - } - } - assert(tc->list() != NULL, "Tree list should be set"); - - inc_totalSize(size); - // Method 'totalSizeInTree' walks through the every block in the - // tree, so it can cause significant performance loss if there are - // many blocks in the tree - assert(!FLSVerifyDictionary || totalSizeInTree(root()) == totalSize(), "_totalSize inconsistency"); - set_totalFreeBlocks(totalFreeBlocks() + 1); - if (FLSVerifyDictionary) { - verifyTree(); - } -} - -size_t BinaryTreeDictionary::maxChunkSize() const { - verify_par_locked(); - TreeList* tc = root(); - if (tc == NULL) return 0; - for (; tc->right() != NULL; tc = tc->right()); - return tc->size(); -} - -size_t BinaryTreeDictionary::totalListLength(TreeList* tl) const { - size_t res; - res = tl->count(); -#ifdef ASSERT - size_t cnt; - FreeChunk* tc = tl->head(); - for (cnt = 0; tc != NULL; tc = tc->next(), cnt++); - assert(res == cnt, "The count is not being maintained correctly"); -#endif - return res; -} - -size_t BinaryTreeDictionary::totalSizeInTree(TreeList* tl) const { - if (tl == NULL) - return 0; - return (tl->size() * totalListLength(tl)) + - totalSizeInTree(tl->left()) + - totalSizeInTree(tl->right()); -} - -double BinaryTreeDictionary::sum_of_squared_block_sizes(TreeList* const tl) const { - if (tl == NULL) { - return 0.0; - } - double size = (double)(tl->size()); - double curr = size * size * totalListLength(tl); - curr += sum_of_squared_block_sizes(tl->left()); - curr += sum_of_squared_block_sizes(tl->right()); - return curr; -} - -size_t BinaryTreeDictionary::totalFreeBlocksInTree(TreeList* tl) const { - if (tl == NULL) - return 0; - return totalListLength(tl) + - totalFreeBlocksInTree(tl->left()) + - totalFreeBlocksInTree(tl->right()); -} - -size_t BinaryTreeDictionary::numFreeBlocks() const { - assert(totalFreeBlocksInTree(root()) == totalFreeBlocks(), - "_totalFreeBlocks inconsistency"); - return totalFreeBlocks(); -} - -size_t BinaryTreeDictionary::treeHeightHelper(TreeList* tl) const { - if (tl == NULL) - return 0; - return 1 + MAX2(treeHeightHelper(tl->left()), - treeHeightHelper(tl->right())); -} - -size_t BinaryTreeDictionary::treeHeight() const { - return treeHeightHelper(root()); -} - -size_t BinaryTreeDictionary::totalNodesHelper(TreeList* tl) const { - if (tl == NULL) { - return 0; - } - return 1 + totalNodesHelper(tl->left()) + - totalNodesHelper(tl->right()); -} - -size_t BinaryTreeDictionary::totalNodesInTree(TreeList* tl) const { - return totalNodesHelper(root()); -} - -void BinaryTreeDictionary::dictCensusUpdate(size_t size, bool split, bool birth){ - TreeList* nd = findList(size); - if (nd) { - if (split) { - if (birth) { - nd->increment_splitBirths(); - nd->increment_surplus(); - } else { - nd->increment_splitDeaths(); - nd->decrement_surplus(); - } - } else { - if (birth) { - nd->increment_coalBirths(); - nd->increment_surplus(); - } else { - nd->increment_coalDeaths(); - nd->decrement_surplus(); - } - } - } - // A list for this size may not be found (nd == 0) if - // This is a death where the appropriate list is now - // empty and has been removed from the list. - // This is a birth associated with a LinAB. The chunk - // for the LinAB is not in the dictionary. -} - -bool BinaryTreeDictionary::coalDictOverPopulated(size_t size) { - if (FLSAlwaysCoalesceLarge) return true; - - TreeList* list_of_size = findList(size); - // None of requested size implies overpopulated. - return list_of_size == NULL || list_of_size->coalDesired() <= 0 || - list_of_size->count() > list_of_size->coalDesired(); -} - -// Closures for walking the binary tree. -// do_list() walks the free list in a node applying the closure -// to each free chunk in the list -// do_tree() walks the nodes in the binary tree applying do_list() -// to each list at each node. - -class TreeCensusClosure : public StackObj { - protected: - virtual void do_list(FreeList* fl) = 0; - public: - virtual void do_tree(TreeList* tl) = 0; -}; - -class AscendTreeCensusClosure : public TreeCensusClosure { - public: - void do_tree(TreeList* tl) { - if (tl != NULL) { - do_tree(tl->left()); - do_list(tl); - do_tree(tl->right()); - } - } -}; - -class DescendTreeCensusClosure : public TreeCensusClosure { - public: - void do_tree(TreeList* tl) { - if (tl != NULL) { - do_tree(tl->right()); - do_list(tl); - do_tree(tl->left()); - } - } -}; - -// For each list in the tree, calculate the desired, desired -// coalesce, count before sweep, and surplus before sweep. -class BeginSweepClosure : public AscendTreeCensusClosure { - double _percentage; - float _inter_sweep_current; - float _inter_sweep_estimate; - float _intra_sweep_estimate; - - public: - BeginSweepClosure(double p, float inter_sweep_current, - float inter_sweep_estimate, - float intra_sweep_estimate) : - _percentage(p), - _inter_sweep_current(inter_sweep_current), - _inter_sweep_estimate(inter_sweep_estimate), - _intra_sweep_estimate(intra_sweep_estimate) { } - - void do_list(FreeList* fl) { - double coalSurplusPercent = _percentage; - fl->compute_desired(_inter_sweep_current, _inter_sweep_estimate, _intra_sweep_estimate); - fl->set_coalDesired((ssize_t)((double)fl->desired() * coalSurplusPercent)); - fl->set_beforeSweep(fl->count()); - fl->set_bfrSurp(fl->surplus()); - } -}; - -// Used to search the tree until a condition is met. -// Similar to TreeCensusClosure but searches the -// tree and returns promptly when found. - -class TreeSearchClosure : public StackObj { - protected: - virtual bool do_list(FreeList* fl) = 0; - public: - virtual bool do_tree(TreeList* tl) = 0; -}; - -#if 0 // Don't need this yet but here for symmetry. -class AscendTreeSearchClosure : public TreeSearchClosure { - public: - bool do_tree(TreeList* tl) { - if (tl != NULL) { - if (do_tree(tl->left())) return true; - if (do_list(tl)) return true; - if (do_tree(tl->right())) return true; - } - return false; - } -}; -#endif - -class DescendTreeSearchClosure : public TreeSearchClosure { - public: - bool do_tree(TreeList* tl) { - if (tl != NULL) { - if (do_tree(tl->right())) return true; - if (do_list(tl)) return true; - if (do_tree(tl->left())) return true; - } - return false; - } -}; - -// Searches the tree for a chunk that ends at the -// specified address. -class EndTreeSearchClosure : public DescendTreeSearchClosure { - HeapWord* _target; - FreeChunk* _found; - - public: - EndTreeSearchClosure(HeapWord* target) : _target(target), _found(NULL) {} - bool do_list(FreeList* fl) { - FreeChunk* item = fl->head(); - while (item != NULL) { - if (item->end() == _target) { - _found = item; - return true; - } - item = item->next(); - } - return false; - } - FreeChunk* found() { return _found; } -}; - -FreeChunk* BinaryTreeDictionary::find_chunk_ends_at(HeapWord* target) const { - EndTreeSearchClosure etsc(target); - bool found_target = etsc.do_tree(root()); - assert(found_target || etsc.found() == NULL, "Consistency check"); - assert(!found_target || etsc.found() != NULL, "Consistency check"); - return etsc.found(); -} - -void BinaryTreeDictionary::beginSweepDictCensus(double coalSurplusPercent, - float inter_sweep_current, float inter_sweep_estimate, float intra_sweep_estimate) { - BeginSweepClosure bsc(coalSurplusPercent, inter_sweep_current, - inter_sweep_estimate, - intra_sweep_estimate); - bsc.do_tree(root()); -} - -// Closures and methods for calculating total bytes returned to the -// free lists in the tree. -NOT_PRODUCT( - class InitializeDictReturnedBytesClosure : public AscendTreeCensusClosure { - public: - void do_list(FreeList* fl) { - fl->set_returnedBytes(0); - } - }; - - void BinaryTreeDictionary::initializeDictReturnedBytes() { - InitializeDictReturnedBytesClosure idrb; - idrb.do_tree(root()); - } - - class ReturnedBytesClosure : public AscendTreeCensusClosure { - size_t _dictReturnedBytes; - public: - ReturnedBytesClosure() { _dictReturnedBytes = 0; } - void do_list(FreeList* fl) { - _dictReturnedBytes += fl->returnedBytes(); - } - size_t dictReturnedBytes() { return _dictReturnedBytes; } - }; - - size_t BinaryTreeDictionary::sumDictReturnedBytes() { - ReturnedBytesClosure rbc; - rbc.do_tree(root()); - - return rbc.dictReturnedBytes(); - } - - // Count the number of entries in the tree. - class treeCountClosure : public DescendTreeCensusClosure { - public: - uint count; - treeCountClosure(uint c) { count = c; } - void do_list(FreeList* fl) { - count++; - } - }; - - size_t BinaryTreeDictionary::totalCount() { - treeCountClosure ctc(0); - ctc.do_tree(root()); - return ctc.count; - } -) - -// Calculate surpluses for the lists in the tree. -class setTreeSurplusClosure : public AscendTreeCensusClosure { - double percentage; - public: - setTreeSurplusClosure(double v) { percentage = v; } - void do_list(FreeList* fl) { - double splitSurplusPercent = percentage; - fl->set_surplus(fl->count() - - (ssize_t)((double)fl->desired() * splitSurplusPercent)); - } -}; - -void BinaryTreeDictionary::setTreeSurplus(double splitSurplusPercent) { - setTreeSurplusClosure sts(splitSurplusPercent); - sts.do_tree(root()); -} - -// Set hints for the lists in the tree. -class setTreeHintsClosure : public DescendTreeCensusClosure { - size_t hint; - public: - setTreeHintsClosure(size_t v) { hint = v; } - void do_list(FreeList* fl) { - fl->set_hint(hint); - assert(fl->hint() == 0 || fl->hint() > fl->size(), - "Current hint is inconsistent"); - if (fl->surplus() > 0) { - hint = fl->size(); - } - } -}; - -void BinaryTreeDictionary::setTreeHints(void) { - setTreeHintsClosure sth(0); - sth.do_tree(root()); -} - -// Save count before previous sweep and splits and coalesces. -class clearTreeCensusClosure : public AscendTreeCensusClosure { - void do_list(FreeList* fl) { - fl->set_prevSweep(fl->count()); - fl->set_coalBirths(0); - fl->set_coalDeaths(0); - fl->set_splitBirths(0); - fl->set_splitDeaths(0); - } -}; - -void BinaryTreeDictionary::clearTreeCensus(void) { - clearTreeCensusClosure ctc; - ctc.do_tree(root()); -} - -// Do reporting and post sweep clean up. -void BinaryTreeDictionary::endSweepDictCensus(double splitSurplusPercent) { - // Does walking the tree 3 times hurt? - setTreeSurplus(splitSurplusPercent); - setTreeHints(); - if (PrintGC && Verbose) { - reportStatistics(); - } - clearTreeCensus(); -} - -// Print summary statistics -void BinaryTreeDictionary::reportStatistics() const { - verify_par_locked(); - gclog_or_tty->print("Statistics for BinaryTreeDictionary:\n" - "------------------------------------\n"); - size_t totalSize = totalChunkSize(debug_only(NULL)); - size_t freeBlocks = numFreeBlocks(); - gclog_or_tty->print("Total Free Space: %d\n", totalSize); - gclog_or_tty->print("Max Chunk Size: %d\n", maxChunkSize()); - gclog_or_tty->print("Number of Blocks: %d\n", freeBlocks); - if (freeBlocks > 0) { - gclog_or_tty->print("Av. Block Size: %d\n", totalSize/freeBlocks); - } - gclog_or_tty->print("Tree Height: %d\n", treeHeight()); -} - -// Print census information - counts, births, deaths, etc. -// for each list in the tree. Also print some summary -// information. -class PrintTreeCensusClosure : public AscendTreeCensusClosure { - int _print_line; - size_t _totalFree; - FreeList _total; - - public: - PrintTreeCensusClosure() { - _print_line = 0; - _totalFree = 0; - } - FreeList* total() { return &_total; } - size_t totalFree() { return _totalFree; } - void do_list(FreeList* fl) { - if (++_print_line >= 40) { - FreeList::print_labels_on(gclog_or_tty, "size"); - _print_line = 0; - } - fl->print_on(gclog_or_tty); - _totalFree += fl->count() * fl->size() ; - total()->set_count( total()->count() + fl->count() ); - total()->set_bfrSurp( total()->bfrSurp() + fl->bfrSurp() ); - total()->set_surplus( total()->splitDeaths() + fl->surplus() ); - total()->set_desired( total()->desired() + fl->desired() ); - total()->set_prevSweep( total()->prevSweep() + fl->prevSweep() ); - total()->set_beforeSweep(total()->beforeSweep() + fl->beforeSweep()); - total()->set_coalBirths( total()->coalBirths() + fl->coalBirths() ); - total()->set_coalDeaths( total()->coalDeaths() + fl->coalDeaths() ); - total()->set_splitBirths(total()->splitBirths() + fl->splitBirths()); - total()->set_splitDeaths(total()->splitDeaths() + fl->splitDeaths()); - } -}; - -void BinaryTreeDictionary::printDictCensus(void) const { - - gclog_or_tty->print("\nBinaryTree\n"); - FreeList::print_labels_on(gclog_or_tty, "size"); - PrintTreeCensusClosure ptc; - ptc.do_tree(root()); - - FreeList* total = ptc.total(); - FreeList::print_labels_on(gclog_or_tty, " "); - total->print_on(gclog_or_tty, "TOTAL\t"); - gclog_or_tty->print( - "totalFree(words): " SIZE_FORMAT_W(16) - " growth: %8.5f deficit: %8.5f\n", - ptc.totalFree(), - (double)(total->splitBirths() + total->coalBirths() - - total->splitDeaths() - total->coalDeaths()) - /(total->prevSweep() != 0 ? (double)total->prevSweep() : 1.0), - (double)(total->desired() - total->count()) - /(total->desired() != 0 ? (double)total->desired() : 1.0)); -} - -class PrintFreeListsClosure : public AscendTreeCensusClosure { - outputStream* _st; - int _print_line; - - public: - PrintFreeListsClosure(outputStream* st) { - _st = st; - _print_line = 0; - } - void do_list(FreeList* fl) { - if (++_print_line >= 40) { - FreeList::print_labels_on(_st, "size"); - _print_line = 0; - } - fl->print_on(gclog_or_tty); - size_t sz = fl->size(); - for (FreeChunk* fc = fl->head(); fc != NULL; - fc = fc->next()) { - _st->print_cr("\t[" PTR_FORMAT "," PTR_FORMAT ") %s", - fc, (HeapWord*)fc + sz, - fc->cantCoalesce() ? "\t CC" : ""); - } - } -}; - -void BinaryTreeDictionary::print_free_lists(outputStream* st) const { - - FreeList::print_labels_on(st, "size"); - PrintFreeListsClosure pflc(st); - pflc.do_tree(root()); -} - -// Verify the following tree invariants: -// . _root has no parent -// . parent and child point to each other -// . each node's key correctly related to that of its child(ren) -void BinaryTreeDictionary::verifyTree() const { - guarantee(root() == NULL || totalFreeBlocks() == 0 || - totalSize() != 0, "_totalSize should't be 0?"); - guarantee(root() == NULL || root()->parent() == NULL, "_root shouldn't have parent"); - verifyTreeHelper(root()); -} - -size_t BinaryTreeDictionary::verifyPrevFreePtrs(TreeList* tl) { - size_t ct = 0; - for (FreeChunk* curFC = tl->head(); curFC != NULL; curFC = curFC->next()) { - ct++; - assert(curFC->prev() == NULL || curFC->prev()->isFree(), - "Chunk should be free"); - } - return ct; -} - -// Note: this helper is recursive rather than iterative, so use with -// caution on very deep trees; and watch out for stack overflow errors; -// In general, to be used only for debugging. -void BinaryTreeDictionary::verifyTreeHelper(TreeList* tl) const { - if (tl == NULL) - return; - guarantee(tl->size() != 0, "A list must has a size"); - guarantee(tl->left() == NULL || tl->left()->parent() == tl, - "parent<-/->left"); - guarantee(tl->right() == NULL || tl->right()->parent() == tl, - "parent<-/->right");; - guarantee(tl->left() == NULL || tl->left()->size() < tl->size(), - "parent !> left"); - guarantee(tl->right() == NULL || tl->right()->size() > tl->size(), - "parent !< left"); - guarantee(tl->head() == NULL || tl->head()->isFree(), "!Free"); - guarantee(tl->head() == NULL || tl->head_as_TreeChunk()->list() == tl, - "list inconsistency"); - guarantee(tl->count() > 0 || (tl->head() == NULL && tl->tail() == NULL), - "list count is inconsistent"); - guarantee(tl->count() > 1 || tl->head() == tl->tail(), - "list is incorrectly constructed"); - size_t count = verifyPrevFreePtrs(tl); - guarantee(count == (size_t)tl->count(), "Node count is incorrect"); - if (tl->head() != NULL) { - tl->head_as_TreeChunk()->verifyTreeChunkList(); - } - verifyTreeHelper(tl->left()); - verifyTreeHelper(tl->right()); -} - -void BinaryTreeDictionary::verify() const { - verifyTree(); - guarantee(totalSize() == totalSizeInTree(root()), "Total Size inconsistency"); -} diff -r e0d32945f6ab -r fa5227d43363 hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/binaryTreeDictionary.hpp --- a/hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/binaryTreeDictionary.hpp Thu May 10 20:05:12 2012 +0400 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,296 +0,0 @@ -/* - * Copyright (c) 2001, 2010, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - * - */ - -#ifndef SHARE_VM_GC_IMPLEMENTATION_CONCURRENTMARKSWEEP_BINARYTREEDICTIONARY_HPP -#define SHARE_VM_GC_IMPLEMENTATION_CONCURRENTMARKSWEEP_BINARYTREEDICTIONARY_HPP - -#include "gc_implementation/concurrentMarkSweep/freeBlockDictionary.hpp" -#include "gc_implementation/concurrentMarkSweep/freeList.hpp" - -/* - * A binary tree based search structure for free blocks. - * This is currently used in the Concurrent Mark&Sweep implementation. - */ - -// A TreeList is a FreeList which can be used to maintain a -// binary tree of free lists. - -class TreeChunk; -class BinaryTreeDictionary; -class AscendTreeCensusClosure; -class DescendTreeCensusClosure; -class DescendTreeSearchClosure; - -class TreeList: public FreeList { - friend class TreeChunk; - friend class BinaryTreeDictionary; - friend class AscendTreeCensusClosure; - friend class DescendTreeCensusClosure; - friend class DescendTreeSearchClosure; - - protected: - TreeList* parent() const { return _parent; } - TreeList* left() const { return _left; } - TreeList* right() const { return _right; } - - // Accessors for links in tree. - - void setLeft(TreeList* tl) { - _left = tl; - if (tl != NULL) - tl->setParent(this); - } - void setRight(TreeList* tl) { - _right = tl; - if (tl != NULL) - tl->setParent(this); - } - void setParent(TreeList* tl) { _parent = tl; } - - void clearLeft() { _left = NULL; } - void clearRight() { _right = NULL; } - void clearParent() { _parent = NULL; } - void initialize() { clearLeft(); clearRight(), clearParent(); } - - // For constructing a TreeList from a Tree chunk or - // address and size. - static TreeList* as_TreeList(TreeChunk* tc); - static TreeList* as_TreeList(HeapWord* addr, size_t size); - - // Returns the head of the free list as a pointer to a TreeChunk. - TreeChunk* head_as_TreeChunk(); - - // Returns the first available chunk in the free list as a pointer - // to a TreeChunk. - TreeChunk* first_available(); - - // Returns the block with the largest heap address amongst - // those in the list for this size; potentially slow and expensive, - // use with caution! - TreeChunk* largest_address(); - - // removeChunkReplaceIfNeeded() removes the given "tc" from the TreeList. - // If "tc" is the first chunk in the list, it is also the - // TreeList that is the node in the tree. removeChunkReplaceIfNeeded() - // returns the possibly replaced TreeList* for the node in - // the tree. It also updates the parent of the original - // node to point to the new node. - TreeList* removeChunkReplaceIfNeeded(TreeChunk* tc); - // See FreeList. - void returnChunkAtHead(TreeChunk* tc); - void returnChunkAtTail(TreeChunk* tc); -}; - -// A TreeChunk is a subclass of a FreeChunk that additionally -// maintains a pointer to the free list on which it is currently -// linked. -// A TreeChunk is also used as a node in the binary tree. This -// allows the binary tree to be maintained without any additional -// storage (the free chunks are used). In a binary tree the first -// chunk in the free list is also the tree node. Note that the -// TreeChunk has an embedded TreeList for this purpose. Because -// the first chunk in the list is distinguished in this fashion -// (also is the node in the tree), it is the last chunk to be found -// on the free list for a node in the tree and is only removed if -// it is the last chunk on the free list. - -class TreeChunk : public FreeChunk { - friend class TreeList; - TreeList* _list; - TreeList _embedded_list; // if non-null, this chunk is on _list - protected: - TreeList* embedded_list() const { return (TreeList*) &_embedded_list; } - void set_embedded_list(TreeList* v) { _embedded_list = *v; } - public: - TreeList* list() { return _list; } - void set_list(TreeList* v) { _list = v; } - static TreeChunk* as_TreeChunk(FreeChunk* fc); - // Initialize fields in a TreeChunk that should be - // initialized when the TreeChunk is being added to - // a free list in the tree. - void initialize() { embedded_list()->initialize(); } - - // debugging - void verifyTreeChunkList() const; -}; - -const size_t MIN_TREE_CHUNK_SIZE = sizeof(TreeChunk)/HeapWordSize; - -class BinaryTreeDictionary: public FreeBlockDictionary { - friend class VMStructs; - bool _splay; - size_t _totalSize; - size_t _totalFreeBlocks; - TreeList* _root; - - // private accessors - bool splay() const { return _splay; } - void set_splay(bool v) { _splay = v; } - size_t totalSize() const { return _totalSize; } - void set_totalSize(size_t v) { _totalSize = v; } - virtual void inc_totalSize(size_t v); - virtual void dec_totalSize(size_t v); - size_t totalFreeBlocks() const { return _totalFreeBlocks; } - void set_totalFreeBlocks(size_t v) { _totalFreeBlocks = v; } - TreeList* root() const { return _root; } - void set_root(TreeList* v) { _root = v; } - - // Remove a chunk of size "size" or larger from the tree and - // return it. If the chunk - // is the last chunk of that size, remove the node for that size - // from the tree. - TreeChunk* getChunkFromTree(size_t size, Dither dither, bool splay); - // Return a list of the specified size or NULL from the tree. - // The list is not removed from the tree. - TreeList* findList (size_t size) const; - // Remove this chunk from the tree. If the removal results - // in an empty list in the tree, remove the empty list. - TreeChunk* removeChunkFromTree(TreeChunk* tc); - // Remove the node in the trees starting at tl that has the - // minimum value and return it. Repair the tree as needed. - TreeList* removeTreeMinimum(TreeList* tl); - void semiSplayStep(TreeList* tl); - // Add this free chunk to the tree. - void insertChunkInTree(FreeChunk* freeChunk); - public: - void verifyTree() const; - // verify that the given chunk is in the tree. - bool verifyChunkInFreeLists(FreeChunk* tc) const; - private: - void verifyTreeHelper(TreeList* tl) const; - static size_t verifyPrevFreePtrs(TreeList* tl); - - // Returns the total number of chunks in the list. - size_t totalListLength(TreeList* tl) const; - // Returns the total number of words in the chunks in the tree - // starting at "tl". - size_t totalSizeInTree(TreeList* tl) const; - // Returns the sum of the square of the size of each block - // in the tree starting at "tl". - double sum_of_squared_block_sizes(TreeList* const tl) const; - // Returns the total number of free blocks in the tree starting - // at "tl". - size_t totalFreeBlocksInTree(TreeList* tl) const; - size_t numFreeBlocks() const; - size_t treeHeight() const; - size_t treeHeightHelper(TreeList* tl) const; - size_t totalNodesInTree(TreeList* tl) const; - size_t totalNodesHelper(TreeList* tl) const; - - public: - // Constructor - BinaryTreeDictionary(MemRegion mr, bool splay = false); - - // Reset the dictionary to the initial conditions with - // a single free chunk. - void reset(MemRegion mr); - void reset(HeapWord* addr, size_t size); - // Reset the dictionary to be empty. - void reset(); - - // Return a chunk of size "size" or greater from - // the tree. - // want a better dynamic splay strategy for the future. - FreeChunk* getChunk(size_t size, Dither dither) { - verify_par_locked(); - FreeChunk* res = getChunkFromTree(size, dither, splay()); - assert(res == NULL || res->isFree(), - "Should be returning a free chunk"); - return res; - } - - void returnChunk(FreeChunk* chunk) { - verify_par_locked(); - insertChunkInTree(chunk); - } - - void removeChunk(FreeChunk* chunk) { - verify_par_locked(); - removeChunkFromTree((TreeChunk*)chunk); - assert(chunk->isFree(), "Should still be a free chunk"); - } - - size_t maxChunkSize() const; - size_t totalChunkSize(debug_only(const Mutex* lock)) const { - debug_only( - if (lock != NULL && lock->owned_by_self()) { - assert(totalSizeInTree(root()) == totalSize(), - "_totalSize inconsistency"); - } - ) - return totalSize(); - } - - size_t minSize() const { - return MIN_TREE_CHUNK_SIZE; - } - - double sum_of_squared_block_sizes() const { - return sum_of_squared_block_sizes(root()); - } - - FreeChunk* find_chunk_ends_at(HeapWord* target) const; - - // Find the list with size "size" in the binary tree and update - // the statistics in the list according to "split" (chunk was - // split or coalesce) and "birth" (chunk was added or removed). - void dictCensusUpdate(size_t size, bool split, bool birth); - // Return true if the dictionary is overpopulated (more chunks of - // this size than desired) for size "size". - bool coalDictOverPopulated(size_t size); - // Methods called at the beginning of a sweep to prepare the - // statistics for the sweep. - void beginSweepDictCensus(double coalSurplusPercent, - float inter_sweep_current, - float inter_sweep_estimate, - float intra_sweep_estimate); - // Methods called after the end of a sweep to modify the - // statistics for the sweep. - void endSweepDictCensus(double splitSurplusPercent); - // Return the largest free chunk in the tree. - FreeChunk* findLargestDict() const; - // Accessors for statistics - void setTreeSurplus(double splitSurplusPercent); - void setTreeHints(void); - // Reset statistics for all the lists in the tree. - void clearTreeCensus(void); - // Print the statistcis for all the lists in the tree. Also may - // print out summaries. - void printDictCensus(void) const; - void print_free_lists(outputStream* st) const; - - // For debugging. Returns the sum of the _returnedBytes for - // all lists in the tree. - size_t sumDictReturnedBytes() PRODUCT_RETURN0; - // Sets the _returnedBytes for all the lists in the tree to zero. - void initializeDictReturnedBytes() PRODUCT_RETURN; - // For debugging. Return the total number of chunks in the dictionary. - size_t totalCount() PRODUCT_RETURN0; - - void reportStatistics() const; - - void verify() const; -}; - -#endif // SHARE_VM_GC_IMPLEMENTATION_CONCURRENTMARKSWEEP_BINARYTREEDICTIONARY_HPP diff -r e0d32945f6ab -r fa5227d43363 hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/cmsPermGen.cpp --- a/hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/cmsPermGen.cpp Thu May 10 20:05:12 2012 +0400 +++ b/hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/cmsPermGen.cpp Thu May 10 11:47:56 2012 -0700 @@ -38,7 +38,7 @@ CMSPermGen::CMSPermGen(ReservedSpace rs, size_t initial_byte_size, CardTableRS* ct, - FreeBlockDictionary::DictionaryChoice dictionaryChoice) { + FreeBlockDictionary::DictionaryChoice dictionaryChoice) { CMSPermGenGen* g = new CMSPermGenGen(rs, initial_byte_size, -1, ct); if (g == NULL) { diff -r e0d32945f6ab -r fa5227d43363 hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/cmsPermGen.hpp --- a/hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/cmsPermGen.hpp Thu May 10 20:05:12 2012 +0400 +++ b/hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/cmsPermGen.hpp Thu May 10 11:47:56 2012 -0700 @@ -45,7 +45,7 @@ public: CMSPermGen(ReservedSpace rs, size_t initial_byte_size, - CardTableRS* ct, FreeBlockDictionary::DictionaryChoice); + CardTableRS* ct, FreeBlockDictionary::DictionaryChoice); HeapWord* mem_allocate(size_t size); @@ -65,7 +65,7 @@ // regarding not using adaptive free lists for a perm gen. ConcurrentMarkSweepGeneration(rs, initial_byte_size, // MinPermHeapExapnsion level, ct, false /* use adaptive freelists */, - (FreeBlockDictionary::DictionaryChoice)CMSDictionaryChoice) + (FreeBlockDictionary::DictionaryChoice)CMSDictionaryChoice) {} void initialize_performance_counters(); diff -r e0d32945f6ab -r fa5227d43363 hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/compactibleFreeListSpace.cpp --- a/hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/compactibleFreeListSpace.cpp Thu May 10 20:05:12 2012 +0400 +++ b/hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/compactibleFreeListSpace.cpp Thu May 10 11:47:56 2012 -0700 @@ -69,7 +69,7 @@ // Constructor CompactibleFreeListSpace::CompactibleFreeListSpace(BlockOffsetSharedArray* bs, MemRegion mr, bool use_adaptive_freelists, - FreeBlockDictionary::DictionaryChoice dictionaryChoice) : + FreeBlockDictionary::DictionaryChoice dictionaryChoice) : _dictionaryChoice(dictionaryChoice), _adaptive_freelists(use_adaptive_freelists), _bt(bs, mr), @@ -87,6 +87,8 @@ CMSConcMarkMultiple), _collector(NULL) { + assert(sizeof(FreeChunk) / BytesPerWord <= MinChunkSize, + "FreeChunk is larger than expected"); _bt.set_space(this); initialize(mr, SpaceDecorator::Clear, SpaceDecorator::Mangle); // We have all of "mr", all of which we place in the dictionary @@ -96,13 +98,13 @@ // implementation, namely, the simple binary tree (splaying // temporarily disabled). switch (dictionaryChoice) { - case FreeBlockDictionary::dictionarySplayTree: - case FreeBlockDictionary::dictionarySkipList: + case FreeBlockDictionary::dictionarySplayTree: + case FreeBlockDictionary::dictionarySkipList: default: warning("dictionaryChoice: selected option not understood; using" " default BinaryTreeDictionary implementation instead."); - case FreeBlockDictionary::dictionaryBinaryTree: - _dictionary = new BinaryTreeDictionary(mr); + case FreeBlockDictionary::dictionaryBinaryTree: + _dictionary = new BinaryTreeDictionary(mr, use_adaptive_freelists); break; } assert(_dictionary != NULL, "CMS dictionary initialization"); @@ -117,7 +119,7 @@ // moved to its new location before the klass is moved. // Set the _refillSize for the linear allocation blocks if (!use_adaptive_freelists) { - FreeChunk* fc = _dictionary->getChunk(mr.word_size()); + FreeChunk* fc = _dictionary->get_chunk(mr.word_size()); // The small linAB initially has all the space and will allocate // a chunk of any size. HeapWord* addr = (HeapWord*) fc; @@ -273,12 +275,12 @@ assert(mr.word_size() >= MinChunkSize, "Chunk size is too small"); _bt.single_block(mr.start(), mr.word_size()); FreeChunk* fc = (FreeChunk*) mr.start(); - fc->setSize(mr.word_size()); + fc->set_size(mr.word_size()); if (mr.word_size() >= IndexSetSize ) { returnChunkToDictionary(fc); } else { _bt.verify_not_unallocated((HeapWord*)fc, fc->size()); - _indexedFreeList[mr.word_size()].returnChunkAtHead(fc); + _indexedFreeList[mr.word_size()].return_chunk_at_head(fc); } } _promoInfo.reset(); @@ -296,7 +298,7 @@ } else { // Place as much of mr in the linAB as we can get, // provided it was big enough to go into the dictionary. - FreeChunk* fc = dictionary()->findLargestDict(); + FreeChunk* fc = dictionary()->find_largest_dict(); if (fc != NULL) { assert(fc->size() == mr.word_size(), "Why was the chunk broken up?"); @@ -323,14 +325,14 @@ #ifndef PRODUCT void CompactibleFreeListSpace::initializeIndexedFreeListArrayReturnedBytes() { for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) { - _indexedFreeList[i].allocation_stats()->set_returnedBytes(0); + _indexedFreeList[i].allocation_stats()->set_returned_bytes(0); } } size_t CompactibleFreeListSpace::sumIndexedFreeListArrayReturnedBytes() { size_t sum = 0; for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) { - sum += _indexedFreeList[i].allocation_stats()->returnedBytes(); + sum += _indexedFreeList[i].allocation_stats()->returned_bytes(); } return sum; } @@ -354,7 +356,7 @@ size_t CompactibleFreeListSpace::totalCount() { size_t num = totalCountInIndexedFreeLists(); - num += dictionary()->totalCount(); + num += dictionary()->total_count(); if (_smallLinearAllocBlock._word_size != 0) { num++; } @@ -364,7 +366,7 @@ bool CompactibleFreeListSpace::is_free_block(const HeapWord* p) const { FreeChunk* fc = (FreeChunk*) p; - return fc->isFree(); + return fc->is_free(); } size_t CompactibleFreeListSpace::used() const { @@ -391,7 +393,7 @@ // that supports jvmstat, and you are apt to see the values // flicker in such cases. assert(_dictionary != NULL, "No _dictionary?"); - return (_dictionary->totalChunkSize(DEBUG_ONLY(freelistLock())) + + return (_dictionary->total_chunk_size(DEBUG_ONLY(freelistLock())) + totalSizeInIndexedFreeLists() + _smallLinearAllocBlock._word_size) * HeapWordSize; } @@ -399,7 +401,7 @@ size_t CompactibleFreeListSpace::max_alloc_in_words() const { assert(_dictionary != NULL, "No _dictionary?"); assert_locked(); - size_t res = _dictionary->maxChunkSize(); + size_t res = _dictionary->max_chunk_size(); res = MAX2(res, MIN2(_smallLinearAllocBlock._word_size, (size_t) SmallForLinearAlloc - 1)); // XXX the following could potentially be pretty slow; @@ -448,7 +450,7 @@ reportIndexedFreeListStatistics(); gclog_or_tty->print_cr("Layout of Indexed Freelists"); gclog_or_tty->print_cr("---------------------------"); - FreeList::print_labels_on(st, "size"); + FreeList::print_labels_on(st, "size"); for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) { _indexedFreeList[i].print_on(gclog_or_tty); for (FreeChunk* fc = _indexedFreeList[i].head(); fc != NULL; @@ -467,7 +469,7 @@ void CompactibleFreeListSpace::print_dictionary_free_lists(outputStream* st) const { - _dictionary->reportStatistics(); + _dictionary->report_statistics(); st->print_cr("Layout of Freelists in Tree"); st->print_cr("---------------------------"); _dictionary->print_free_lists(st); @@ -545,12 +547,12 @@ void CompactibleFreeListSpace::reportFreeListStatistics() const { assert_lock_strong(&_freelistLock); assert(PrintFLSStatistics != 0, "Reporting error"); - _dictionary->reportStatistics(); + _dictionary->report_statistics(); if (PrintFLSStatistics > 1) { reportIndexedFreeListStatistics(); - size_t totalSize = totalSizeInIndexedFreeLists() + - _dictionary->totalChunkSize(DEBUG_ONLY(freelistLock())); - gclog_or_tty->print(" free=%ld frag=%1.4f\n", totalSize, flsFrag()); + size_t total_size = totalSizeInIndexedFreeLists() + + _dictionary->total_chunk_size(DEBUG_ONLY(freelistLock())); + gclog_or_tty->print(" free=%ld frag=%1.4f\n", total_size, flsFrag()); } } @@ -558,13 +560,13 @@ assert_lock_strong(&_freelistLock); gclog_or_tty->print("Statistics for IndexedFreeLists:\n" "--------------------------------\n"); - size_t totalSize = totalSizeInIndexedFreeLists(); - size_t freeBlocks = numFreeBlocksInIndexedFreeLists(); - gclog_or_tty->print("Total Free Space: %d\n", totalSize); + size_t total_size = totalSizeInIndexedFreeLists(); + size_t free_blocks = numFreeBlocksInIndexedFreeLists(); + gclog_or_tty->print("Total Free Space: %d\n", total_size); gclog_or_tty->print("Max Chunk Size: %d\n", maxChunkSizeInIndexedFreeLists()); - gclog_or_tty->print("Number of Blocks: %d\n", freeBlocks); - if (freeBlocks != 0) { - gclog_or_tty->print("Av. Block Size: %d\n", totalSize/freeBlocks); + gclog_or_tty->print("Number of Blocks: %d\n", free_blocks); + if (free_blocks != 0) { + gclog_or_tty->print("Av. Block Size: %d\n", total_size/free_blocks); } } @@ -911,7 +913,7 @@ for (addr = bottom(), last = end(); addr < last; addr += size) { FreeChunk* fc = (FreeChunk*)addr; - if (fc->isFree()) { + if (fc->is_free()) { // Since we hold the free list lock, which protects direct // allocation in this generation by mutators, a free object // will remain free throughout this iteration code. @@ -953,7 +955,7 @@ for (addr = block_start_careful(mr.start()), end = mr.end(); addr < end; addr += size) { FreeChunk* fc = (FreeChunk*)addr; - if (fc->isFree()) { + if (fc->is_free()) { // Since we hold the free list lock, which protects direct // allocation in this generation by mutators, a free object // will remain free throughout this iteration code. @@ -1069,7 +1071,7 @@ NOT_PRODUCT(verify_objects_initialized()); assert(MemRegion(bottom(), end()).contains(p), "p not in space"); FreeChunk* fc = (FreeChunk*)p; - if (fc->isFree()) { + if (fc->is_free()) { return fc->size(); } else { // Ignore mark word because this may be a recently promoted @@ -1160,7 +1162,7 @@ FreeChunk* fc = (FreeChunk*)p; assert(is_in_reserved(p), "Should be in space"); assert(_bt.block_start(p) == p, "Should be a block boundary"); - if (!fc->isFree()) { + if (!fc->is_free()) { // Ignore mark word because it may have been used to // chain together promoted objects (the last one // would have a null value). @@ -1222,7 +1224,7 @@ FreeChunk* fc = (FreeChunk*)res; fc->markNotFree(); - assert(!fc->isFree(), "shouldn't be marked free"); + assert(!fc->is_free(), "shouldn't be marked free"); assert(oop(fc)->klass_or_null() == NULL, "should look uninitialized"); // Verify that the block offset table shows this to // be a single block, but not one which is unallocated. @@ -1331,10 +1333,10 @@ size_t currSize = numWords + MinChunkSize; assert(currSize % MinObjAlignment == 0, "currSize should be aligned"); for (i = currSize; i < IndexSetSize; i += IndexSetStride) { - FreeList* fl = &_indexedFreeList[i]; + FreeList* fl = &_indexedFreeList[i]; if (fl->head()) { ret = getFromListGreater(fl, numWords); - assert(ret == NULL || ret->isFree(), "Should be returning a free chunk"); + assert(ret == NULL || ret->is_free(), "Should be returning a free chunk"); return ret; } } @@ -1345,7 +1347,7 @@ /* Try to get a chunk that satisfies request, while avoiding fragmentation that can't be handled. */ { - ret = dictionary()->getChunk(currSize); + ret = dictionary()->get_chunk(currSize); if (ret != NULL) { assert(ret->size() - numWords >= MinChunkSize, "Chunk is too small"); @@ -1353,10 +1355,10 @@ /* Carve returned chunk. */ (void) splitChunkAndReturnRemainder(ret, numWords); /* Label this as no longer a free chunk. */ - assert(ret->isFree(), "This chunk should be free"); - ret->linkPrev(NULL); + assert(ret->is_free(), "This chunk should be free"); + ret->link_prev(NULL); } - assert(ret == NULL || ret->isFree(), "Should be returning a free chunk"); + assert(ret == NULL || ret->is_free(), "Should be returning a free chunk"); return ret; } ShouldNotReachHere(); @@ -1364,7 +1366,7 @@ bool CompactibleFreeListSpace::verifyChunkInIndexedFreeLists(FreeChunk* fc) const { assert(fc->size() < IndexSetSize, "Size of chunk is too large"); - return _indexedFreeList[fc->size()].verifyChunkInFreeLists(fc); + return _indexedFreeList[fc->size()].verify_chunk_in_free_list(fc); } bool CompactibleFreeListSpace::verify_chunk_is_linear_alloc_block(FreeChunk* fc) const { @@ -1378,13 +1380,13 @@ // Check if the purported free chunk is present either as a linear // allocation block, the size-indexed table of (smaller) free blocks, // or the larger free blocks kept in the binary tree dictionary. -bool CompactibleFreeListSpace::verifyChunkInFreeLists(FreeChunk* fc) const { +bool CompactibleFreeListSpace::verify_chunk_in_free_list(FreeChunk* fc) const { if (verify_chunk_is_linear_alloc_block(fc)) { return true; } else if (fc->size() < IndexSetSize) { return verifyChunkInIndexedFreeLists(fc); } else { - return dictionary()->verifyChunkInFreeLists(fc); + return dictionary()->verify_chunk_in_free_list(fc); } } @@ -1412,7 +1414,7 @@ } if (fc != NULL) { fc->dontCoalesce(); - assert(fc->isFree(), "Should be free, but not coalescable"); + assert(fc->is_free(), "Should be free, but not coalescable"); // Verify that the block offset table shows this to // be a single block, but not one which is unallocated. _bt.verify_single_block((HeapWord*)fc, fc->size()); @@ -1492,7 +1494,7 @@ } // Return the chunk that isn't big enough, and then refill below. addChunkToFreeLists(blk->_ptr, sz); - splitBirth(sz); + split_birth(sz); // Don't keep statistics on adding back chunk from a LinAB. } else { // A refilled block would not satisfy the request. @@ -1504,14 +1506,14 @@ assert(blk->_ptr == NULL || blk->_word_size >= size + MinChunkSize, "block was replenished"); if (res != NULL) { - splitBirth(size); + split_birth(size); repairLinearAllocBlock(blk); } else if (blk->_ptr != NULL) { res = blk->_ptr; size_t blk_size = blk->_word_size; blk->_word_size -= size; blk->_ptr += size; - splitBirth(size); + split_birth(size); repairLinearAllocBlock(blk); // Update BOT last so that other (parallel) GC threads see a consistent // view of the BOT and free blocks. @@ -1540,7 +1542,7 @@ size_t blk_size = blk->_word_size; blk->_word_size -= size; blk->_ptr += size; - splitBirth(size); + split_birth(size); repairLinearAllocBlock(blk); // Update BOT last so that other (parallel) GC threads see a consistent // view of the BOT and free blocks. @@ -1557,7 +1559,7 @@ assert_locked(); assert(size < SmallForDictionary, "just checking"); FreeChunk* res; - res = _indexedFreeList[size].getChunkAtHead(); + res = _indexedFreeList[size].get_chunk_at_head(); if (res == NULL) { res = getChunkFromIndexedFreeListHelper(size); } @@ -1591,7 +1593,7 @@ // Do not replenish from an underpopulated size. if (_indexedFreeList[replenish_size].surplus() > 0 && _indexedFreeList[replenish_size].head() != NULL) { - newFc = _indexedFreeList[replenish_size].getChunkAtHead(); + newFc = _indexedFreeList[replenish_size].get_chunk_at_head(); } else if (bestFitFirst()) { newFc = bestFitSmall(replenish_size); } @@ -1624,13 +1626,13 @@ i < (num_blk - 1); curFc = nextFc, nextFc = (FreeChunk*)((HeapWord*)nextFc + size), i++) { - curFc->setSize(size); + curFc->set_size(size); // Don't record this as a return in order to try and // determine the "returns" from a GC. _bt.verify_not_unallocated((HeapWord*) fc, size); - _indexedFreeList[size].returnChunkAtTail(curFc, false); + _indexedFreeList[size].return_chunk_at_tail(curFc, false); _bt.mark_block((HeapWord*)curFc, size); - splitBirth(size); + split_birth(size); // Don't record the initial population of the indexed list // as a split birth. } @@ -1638,9 +1640,9 @@ // check that the arithmetic was OK above assert((HeapWord*)nextFc == (HeapWord*)newFc + num_blk*size, "inconsistency in carving newFc"); - curFc->setSize(size); + curFc->set_size(size); _bt.mark_block((HeapWord*)curFc, size); - splitBirth(size); + split_birth(size); fc = curFc; } else { // Return entire block to caller @@ -1653,14 +1655,14 @@ // replenish the indexed free list. fc = getChunkFromDictionaryExact(size); } - // assert(fc == NULL || fc->isFree(), "Should be returning a free chunk"); + // assert(fc == NULL || fc->is_free(), "Should be returning a free chunk"); return fc; } FreeChunk* CompactibleFreeListSpace::getChunkFromDictionary(size_t size) { assert_locked(); - FreeChunk* fc = _dictionary->getChunk(size); + FreeChunk* fc = _dictionary->get_chunk(size); if (fc == NULL) { return NULL; } @@ -1677,7 +1679,7 @@ FreeChunk* CompactibleFreeListSpace::getChunkFromDictionaryExact(size_t size) { assert_locked(); - FreeChunk* fc = _dictionary->getChunk(size); + FreeChunk* fc = _dictionary->get_chunk(size); if (fc == NULL) { return fc; } @@ -1686,11 +1688,11 @@ _bt.verify_single_block((HeapWord*)fc, size); return fc; } - assert(fc->size() > size, "getChunk() guarantee"); + assert(fc->size() > size, "get_chunk() guarantee"); if (fc->size() < size + MinChunkSize) { // Return the chunk to the dictionary and go get a bigger one. returnChunkToDictionary(fc); - fc = _dictionary->getChunk(size + MinChunkSize); + fc = _dictionary->get_chunk(size + MinChunkSize); if (fc == NULL) { return NULL; } @@ -1711,10 +1713,10 @@ _bt.verify_single_block((HeapWord*)chunk, size); // adjust _unallocated_block downward, as necessary _bt.freed((HeapWord*)chunk, size); - _dictionary->returnChunk(chunk); + _dictionary->return_chunk(chunk); #ifndef PRODUCT if (CMSCollector::abstract_state() != CMSCollector::Sweeping) { - TreeChunk::as_TreeChunk(chunk)->list()->verify_stats(); + TreeChunk::as_TreeChunk(chunk)->list()->verify_stats(); } #endif // PRODUCT } @@ -1726,9 +1728,9 @@ _bt.verify_single_block((HeapWord*) fc, size); _bt.verify_not_unallocated((HeapWord*) fc, size); if (_adaptive_freelists) { - _indexedFreeList[size].returnChunkAtTail(fc); + _indexedFreeList[size].return_chunk_at_tail(fc); } else { - _indexedFreeList[size].returnChunkAtHead(fc); + _indexedFreeList[size].return_chunk_at_head(fc); } #ifndef PRODUCT if (CMSCollector::abstract_state() != CMSCollector::Sweeping) { @@ -1756,7 +1758,7 @@ FreeChunk* ec; { MutexLockerEx x(lock, Mutex::_no_safepoint_check_flag); - ec = dictionary()->findLargestDict(); // get largest block + ec = dictionary()->find_largest_dict(); // get largest block if (ec != NULL && ec->end() == chunk) { // It's a coterminal block - we can coalesce. size_t old_size = ec->size(); @@ -1767,7 +1769,7 @@ ec = (FreeChunk*)chunk; } } - ec->setSize(size); + ec->set_size(size); debug_only(ec->mangleFreed(size)); if (size < SmallForDictionary) { lock = _indexedFreeListParLocks[size]; @@ -1790,7 +1792,7 @@ _bt.verify_single_block(chunk, size); FreeChunk* fc = (FreeChunk*) chunk; - fc->setSize(size); + fc->set_size(size); debug_only(fc->mangleFreed(size)); if (size < SmallForDictionary) { returnChunkToFreeList(fc); @@ -1833,7 +1835,7 @@ assert_locked(); assert(fc != NULL, "null chunk"); _bt.verify_single_block((HeapWord*)fc, size); - _dictionary->removeChunk(fc); + _dictionary->remove_chunk(fc); // adjust _unallocated_block upward, as necessary _bt.allocated((HeapWord*)fc, size); } @@ -1848,7 +1850,7 @@ verifyIndexedFreeList(size); } ) - _indexedFreeList[size].removeChunk(fc); + _indexedFreeList[size].remove_chunk(fc); NOT_PRODUCT( if (FLSVerifyIndexTable) { verifyIndexedFreeList(size); @@ -1862,17 +1864,17 @@ the excess is >= MIN_CHUNK. */ size_t start = align_object_size(numWords + MinChunkSize); if (start < IndexSetSize) { - FreeList* it = _indexedFreeList; + FreeList* it = _indexedFreeList; size_t hint = _indexedFreeList[start].hint(); while (hint < IndexSetSize) { assert(hint % MinObjAlignment == 0, "hint should be aligned"); - FreeList *fl = &_indexedFreeList[hint]; + FreeList *fl = &_indexedFreeList[hint]; if (fl->surplus() > 0 && fl->head() != NULL) { // Found a list with surplus, reset original hint // and split out a free chunk which is returned. _indexedFreeList[start].set_hint(hint); FreeChunk* res = getFromListGreater(fl, numWords); - assert(res == NULL || res->isFree(), + assert(res == NULL || res->is_free(), "Should be returning a free chunk"); return res; } @@ -1885,7 +1887,7 @@ } /* Requires fl->size >= numWords + MinChunkSize */ -FreeChunk* CompactibleFreeListSpace::getFromListGreater(FreeList* fl, +FreeChunk* CompactibleFreeListSpace::getFromListGreater(FreeList* fl, size_t numWords) { FreeChunk *curr = fl->head(); size_t oldNumWords = curr->size(); @@ -1894,13 +1896,13 @@ assert(oldNumWords >= numWords + MinChunkSize, "Size of chunks in the list is too small"); - fl->removeChunk(curr); + fl->remove_chunk(curr); // recorded indirectly by splitChunkAndReturnRemainder - // smallSplit(oldNumWords, numWords); FreeChunk* new_chunk = splitChunkAndReturnRemainder(curr, numWords); // Does anything have to be done for the remainder in terms of // fixing the card table? - assert(new_chunk == NULL || new_chunk->isFree(), + assert(new_chunk == NULL || new_chunk->is_free(), "Should be returning a free chunk"); return new_chunk; } @@ -1918,13 +1920,13 @@ assert(rem_size >= MinChunkSize, "Free chunk smaller than minimum"); FreeChunk* ffc = (FreeChunk*)((HeapWord*)chunk + new_size); assert(is_aligned(ffc), "alignment problem"); - ffc->setSize(rem_size); - ffc->linkNext(NULL); - ffc->linkPrev(NULL); // Mark as a free block for other (parallel) GC threads. + ffc->set_size(rem_size); + ffc->link_next(NULL); + ffc->link_prev(NULL); // Mark as a free block for other (parallel) GC threads. // Above must occur before BOT is updated below. // adjust block offset table OrderAccess::storestore(); - assert(chunk->isFree() && ffc->isFree(), "Error"); + assert(chunk->is_free() && ffc->is_free(), "Error"); _bt.split_block((HeapWord*)chunk, chunk->size(), new_size); if (rem_size < SmallForDictionary) { bool is_par = (SharedHeap::heap()->n_par_threads() > 0); @@ -1939,7 +1941,7 @@ returnChunkToDictionary(ffc); split(size ,rem_size); } - chunk->setSize(new_size); + chunk->set_size(new_size); return chunk; } @@ -2046,10 +2048,10 @@ assert(blk->_word_size != 0 && blk->_word_size >= MinChunkSize, "Minimum block size requirement"); FreeChunk* fc = (FreeChunk*)(blk->_ptr); - fc->setSize(blk->_word_size); - fc->linkPrev(NULL); // mark as free + fc->set_size(blk->_word_size); + fc->link_prev(NULL); // mark as free fc->dontCoalesce(); - assert(fc->isFree(), "just marked it free"); + assert(fc->is_free(), "just marked it free"); assert(fc->cantCoalesce(), "just marked it uncoalescable"); } } @@ -2149,7 +2151,7 @@ } double totFree = itabFree + - _dictionary->totalChunkSize(DEBUG_ONLY(freelistLock())); + _dictionary->total_chunk_size(DEBUG_ONLY(freelistLock())); if (totFree > 0) { frag = ((frag + _dictionary->sum_of_squared_block_sizes()) / (totFree * totFree)); @@ -2167,16 +2169,16 @@ assert_locked(); size_t i; for (i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) { - FreeList* fl = &_indexedFreeList[i]; + FreeList* fl = &_indexedFreeList[i]; if (PrintFLSStatistics > 1) { gclog_or_tty->print("size[%d] : ", i); } fl->compute_desired(inter_sweep_current, inter_sweep_estimate, intra_sweep_estimate); - fl->set_coalDesired((ssize_t)((double)fl->desired() * CMSSmallCoalSurplusPercent)); - fl->set_beforeSweep(fl->count()); - fl->set_bfrSurp(fl->surplus()); + fl->set_coal_desired((ssize_t)((double)fl->desired() * CMSSmallCoalSurplusPercent)); + fl->set_before_sweep(fl->count()); + fl->set_bfr_surp(fl->surplus()); } - _dictionary->beginSweepDictCensus(CMSLargeCoalSurplusPercent, + _dictionary->begin_sweep_dict_census(CMSLargeCoalSurplusPercent, inter_sweep_current, inter_sweep_estimate, intra_sweep_estimate); @@ -2186,7 +2188,7 @@ assert_locked(); size_t i; for (i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) { - FreeList *fl = &_indexedFreeList[i]; + FreeList *fl = &_indexedFreeList[i]; fl->set_surplus(fl->count() - (ssize_t)((double)fl->desired() * CMSSmallSplitSurplusPercent)); } @@ -2197,7 +2199,7 @@ size_t i; size_t h = IndexSetSize; for (i = IndexSetSize - 1; i != 0; i -= IndexSetStride) { - FreeList *fl = &_indexedFreeList[i]; + FreeList *fl = &_indexedFreeList[i]; fl->set_hint(h); if (fl->surplus() > 0) { h = i; @@ -2209,18 +2211,18 @@ assert_locked(); size_t i; for (i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) { - FreeList *fl = &_indexedFreeList[i]; - fl->set_prevSweep(fl->count()); - fl->set_coalBirths(0); - fl->set_coalDeaths(0); - fl->set_splitBirths(0); - fl->set_splitDeaths(0); + FreeList *fl = &_indexedFreeList[i]; + fl->set_prev_sweep(fl->count()); + fl->set_coal_births(0); + fl->set_coal_deaths(0); + fl->set_split_births(0); + fl->set_split_deaths(0); } } void CompactibleFreeListSpace::endSweepFLCensus(size_t sweep_count) { if (PrintFLSStatistics > 0) { - HeapWord* largestAddr = (HeapWord*) dictionary()->findLargestDict(); + HeapWord* largestAddr = (HeapWord*) dictionary()->find_largest_dict(); gclog_or_tty->print_cr("CMS: Large block " PTR_FORMAT, largestAddr); } @@ -2231,30 +2233,30 @@ } clearFLCensus(); assert_locked(); - _dictionary->endSweepDictCensus(CMSLargeSplitSurplusPercent); + _dictionary->end_sweep_dict_census(CMSLargeSplitSurplusPercent); } bool CompactibleFreeListSpace::coalOverPopulated(size_t size) { if (size < SmallForDictionary) { - FreeList *fl = &_indexedFreeList[size]; - return (fl->coalDesired() < 0) || - ((int)fl->count() > fl->coalDesired()); + FreeList *fl = &_indexedFreeList[size]; + return (fl->coal_desired() < 0) || + ((int)fl->count() > fl->coal_desired()); } else { - return dictionary()->coalDictOverPopulated(size); + return dictionary()->coal_dict_over_populated(size); } } void CompactibleFreeListSpace::smallCoalBirth(size_t size) { assert(size < SmallForDictionary, "Size too large for indexed list"); - FreeList *fl = &_indexedFreeList[size]; - fl->increment_coalBirths(); + FreeList *fl = &_indexedFreeList[size]; + fl->increment_coal_births(); fl->increment_surplus(); } void CompactibleFreeListSpace::smallCoalDeath(size_t size) { assert(size < SmallForDictionary, "Size too large for indexed list"); - FreeList *fl = &_indexedFreeList[size]; - fl->increment_coalDeaths(); + FreeList *fl = &_indexedFreeList[size]; + fl->increment_coal_deaths(); fl->decrement_surplus(); } @@ -2262,7 +2264,7 @@ if (size < SmallForDictionary) { smallCoalBirth(size); } else { - dictionary()->dictCensusUpdate(size, + dictionary()->dict_census_udpate(size, false /* split */, true /* birth */); } @@ -2272,7 +2274,7 @@ if(size < SmallForDictionary) { smallCoalDeath(size); } else { - dictionary()->dictCensusUpdate(size, + dictionary()->dict_census_udpate(size, false /* split */, false /* birth */); } @@ -2280,23 +2282,23 @@ void CompactibleFreeListSpace::smallSplitBirth(size_t size) { assert(size < SmallForDictionary, "Size too large for indexed list"); - FreeList *fl = &_indexedFreeList[size]; - fl->increment_splitBirths(); + FreeList *fl = &_indexedFreeList[size]; + fl->increment_split_births(); fl->increment_surplus(); } void CompactibleFreeListSpace::smallSplitDeath(size_t size) { assert(size < SmallForDictionary, "Size too large for indexed list"); - FreeList *fl = &_indexedFreeList[size]; - fl->increment_splitDeaths(); + FreeList *fl = &_indexedFreeList[size]; + fl->increment_split_deaths(); fl->decrement_surplus(); } -void CompactibleFreeListSpace::splitBirth(size_t size) { +void CompactibleFreeListSpace::split_birth(size_t size) { if (size < SmallForDictionary) { smallSplitBirth(size); } else { - dictionary()->dictCensusUpdate(size, + dictionary()->dict_census_udpate(size, true /* split */, true /* birth */); } @@ -2306,7 +2308,7 @@ if (size < SmallForDictionary) { smallSplitDeath(size); } else { - dictionary()->dictCensusUpdate(size, + dictionary()->dict_census_udpate(size, true /* split */, false /* birth */); } @@ -2315,8 +2317,8 @@ void CompactibleFreeListSpace::split(size_t from, size_t to1) { size_t to2 = from - to1; splitDeath(from); - splitBirth(to1); - splitBirth(to2); + split_birth(to1); + split_birth(to2); } void CompactibleFreeListSpace::print() const { @@ -2362,7 +2364,7 @@ FreeChunk* fc = (FreeChunk*)addr; res = fc->size(); if (FLSVerifyLists && !fc->cantCoalesce()) { - guarantee(_sp->verifyChunkInFreeLists(fc), + guarantee(_sp->verify_chunk_in_free_list(fc), "Chunk should be on a free list"); } } @@ -2518,7 +2520,7 @@ "Slot should have been empty"); for (; fc != NULL; fc = fc->next(), n++) { guarantee(fc->size() == size, "Size inconsistency"); - guarantee(fc->isFree(), "!free?"); + guarantee(fc->is_free(), "!free?"); guarantee(fc->next() == NULL || fc->next()->prev() == fc, "Broken list"); guarantee((fc->next() == NULL) == (fc == tail), "Incorrect tail"); } @@ -2527,10 +2529,10 @@ #ifndef PRODUCT void CompactibleFreeListSpace::check_free_list_consistency() const { - assert(_dictionary->minSize() <= IndexSetSize, + assert(_dictionary->min_size() <= IndexSetSize, "Some sizes can't be allocated without recourse to" " linear allocation buffers"); - assert(MIN_TREE_CHUNK_SIZE*HeapWordSize == sizeof(TreeChunk), + assert(BinaryTreeDictionary::min_tree_chunk_size*HeapWordSize == sizeof(TreeChunk), "else MIN_TREE_CHUNK_SIZE is wrong"); assert((IndexSetStride == 2 && IndexSetStart == 4) || // 32-bit (IndexSetStride == 1 && IndexSetStart == 3), "just checking"); // 64-bit @@ -2543,36 +2545,36 @@ void CompactibleFreeListSpace::printFLCensus(size_t sweep_count) const { assert_lock_strong(&_freelistLock); - FreeList total; + FreeList total; gclog_or_tty->print("end sweep# " SIZE_FORMAT "\n", sweep_count); - FreeList::print_labels_on(gclog_or_tty, "size"); - size_t totalFree = 0; + FreeList::print_labels_on(gclog_or_tty, "size"); + size_t total_free = 0; for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) { - const FreeList *fl = &_indexedFreeList[i]; - totalFree += fl->count() * fl->size(); + const FreeList *fl = &_indexedFreeList[i]; + total_free += fl->count() * fl->size(); if (i % (40*IndexSetStride) == 0) { - FreeList::print_labels_on(gclog_or_tty, "size"); + FreeList::print_labels_on(gclog_or_tty, "size"); } fl->print_on(gclog_or_tty); - total.set_bfrSurp( total.bfrSurp() + fl->bfrSurp() ); + total.set_bfr_surp( total.bfr_surp() + fl->bfr_surp() ); total.set_surplus( total.surplus() + fl->surplus() ); total.set_desired( total.desired() + fl->desired() ); - total.set_prevSweep( total.prevSweep() + fl->prevSweep() ); - total.set_beforeSweep(total.beforeSweep() + fl->beforeSweep()); + total.set_prev_sweep( total.prev_sweep() + fl->prev_sweep() ); + total.set_before_sweep(total.before_sweep() + fl->before_sweep()); total.set_count( total.count() + fl->count() ); - total.set_coalBirths( total.coalBirths() + fl->coalBirths() ); - total.set_coalDeaths( total.coalDeaths() + fl->coalDeaths() ); - total.set_splitBirths(total.splitBirths() + fl->splitBirths()); - total.set_splitDeaths(total.splitDeaths() + fl->splitDeaths()); + total.set_coal_births( total.coal_births() + fl->coal_births() ); + total.set_coal_deaths( total.coal_deaths() + fl->coal_deaths() ); + total.set_split_births(total.split_births() + fl->split_births()); + total.set_split_deaths(total.split_deaths() + fl->split_deaths()); } total.print_on(gclog_or_tty, "TOTAL"); gclog_or_tty->print_cr("Total free in indexed lists " - SIZE_FORMAT " words", totalFree); + SIZE_FORMAT " words", total_free); gclog_or_tty->print("growth: %8.5f deficit: %8.5f\n", - (double)(total.splitBirths()+total.coalBirths()-total.splitDeaths()-total.coalDeaths())/ - (total.prevSweep() != 0 ? (double)total.prevSweep() : 1.0), + (double)(total.split_births()+total.coal_births()-total.split_deaths()-total.coal_deaths())/ + (total.prev_sweep() != 0 ? (double)total.prev_sweep() : 1.0), (double)(total.desired() - total.count())/(total.desired() != 0 ? (double)total.desired() : 1.0)); - _dictionary->printDictCensus(); + _dictionary->print_dict_census(); } /////////////////////////////////////////////////////////////////////////// @@ -2634,18 +2636,18 @@ res = _cfls->getChunkFromDictionaryExact(word_sz); if (res == NULL) return NULL; } else { - FreeList* fl = &_indexedFreeList[word_sz]; + FreeList* fl = &_indexedFreeList[word_sz]; if (fl->count() == 0) { // Attempt to refill this local free list. get_from_global_pool(word_sz, fl); // If it didn't work, give up. if (fl->count() == 0) return NULL; } - res = fl->getChunkAtHead(); + res = fl->get_chunk_at_head(); assert(res != NULL, "Why was count non-zero?"); } res->markNotFree(); - assert(!res->isFree(), "shouldn't be marked free"); + assert(!res->is_free(), "shouldn't be marked free"); assert(oop(res)->klass_or_null() == NULL, "should look uninitialized"); // mangle a just allocated object with a distinct pattern. debug_only(res->mangleAllocated(word_sz)); @@ -2654,7 +2656,7 @@ // Get a chunk of blocks of the right size and update related // book-keeping stats -void CFLS_LAB::get_from_global_pool(size_t word_sz, FreeList* fl) { +void CFLS_LAB::get_from_global_pool(size_t word_sz, FreeList* fl) { // Get the #blocks we want to claim size_t n_blks = (size_t)_blocks_to_claim[word_sz].average(); assert(n_blks > 0, "Error"); @@ -2736,7 +2738,7 @@ if (num_retire > 0) { _cfls->_indexedFreeList[i].prepend(&_indexedFreeList[i]); // Reset this list. - _indexedFreeList[i] = FreeList(); + _indexedFreeList[i] = FreeList(); _indexedFreeList[i].set_size(i); } } @@ -2750,7 +2752,7 @@ } } -void CompactibleFreeListSpace:: par_get_chunk_of_blocks(size_t word_sz, size_t n, FreeList* fl) { +void CompactibleFreeListSpace:: par_get_chunk_of_blocks(size_t word_sz, size_t n, FreeList* fl) { assert(fl->count() == 0, "Precondition."); assert(word_sz < CompactibleFreeListSpace::IndexSetSize, "Precondition"); @@ -2766,12 +2768,12 @@ (cur_sz < CompactibleFreeListSpace::IndexSetSize) && (CMSSplitIndexedFreeListBlocks || k <= 1); k++, cur_sz = k * word_sz) { - FreeList fl_for_cur_sz; // Empty. + FreeList fl_for_cur_sz; // Empty. fl_for_cur_sz.set_size(cur_sz); { MutexLockerEx x(_indexedFreeListParLocks[cur_sz], Mutex::_no_safepoint_check_flag); - FreeList* gfl = &_indexedFreeList[cur_sz]; + FreeList* gfl = &_indexedFreeList[cur_sz]; if (gfl->count() != 0) { // nn is the number of chunks of size cur_sz that // we'd need to split k-ways each, in order to create @@ -2784,9 +2786,9 @@ // we increment the split death count by the number of blocks // we just took from the cur_sz-size blocks list and which // we will be splitting below. - ssize_t deaths = gfl->splitDeaths() + + ssize_t deaths = gfl->split_deaths() + fl_for_cur_sz.count(); - gfl->set_splitDeaths(deaths); + gfl->set_split_deaths(deaths); } } } @@ -2797,21 +2799,21 @@ } else { // Divide each block on fl_for_cur_sz up k ways. FreeChunk* fc; - while ((fc = fl_for_cur_sz.getChunkAtHead()) != NULL) { + while ((fc = fl_for_cur_sz.get_chunk_at_head()) != NULL) { // Must do this in reverse order, so that anybody attempting to // access the main chunk sees it as a single free block until we // change it. size_t fc_size = fc->size(); - assert(fc->isFree(), "Error"); + assert(fc->is_free(), "Error"); for (int i = k-1; i >= 0; i--) { FreeChunk* ffc = (FreeChunk*)((HeapWord*)fc + i * word_sz); assert((i != 0) || - ((fc == ffc) && ffc->isFree() && + ((fc == ffc) && ffc->is_free() && (ffc->size() == k*word_sz) && (fc_size == word_sz)), "Counting error"); - ffc->setSize(word_sz); - ffc->linkPrev(NULL); // Mark as a free block for other (parallel) GC threads. - ffc->linkNext(NULL); + ffc->set_size(word_sz); + ffc->link_prev(NULL); // Mark as a free block for other (parallel) GC threads. + ffc->link_next(NULL); // Above must occur before BOT is updated below. OrderAccess::storestore(); // splitting from the right, fc_size == i * word_sz @@ -2822,7 +2824,7 @@ _bt.verify_single_block((HeapWord*)fc, fc_size); _bt.verify_single_block((HeapWord*)ffc, word_sz); // Push this on "fl". - fl->returnChunkAtHead(ffc); + fl->return_chunk_at_head(ffc); } // TRAP assert(fl->tail()->next() == NULL, "List invariant."); @@ -2832,8 +2834,8 @@ size_t num = fl->count(); MutexLockerEx x(_indexedFreeListParLocks[word_sz], Mutex::_no_safepoint_check_flag); - ssize_t births = _indexedFreeList[word_sz].splitBirths() + num; - _indexedFreeList[word_sz].set_splitBirths(births); + ssize_t births = _indexedFreeList[word_sz].split_births() + num; + _indexedFreeList[word_sz].set_split_births(births); return; } } @@ -2846,12 +2848,12 @@ MutexLockerEx x(parDictionaryAllocLock(), Mutex::_no_safepoint_check_flag); while (n > 0) { - fc = dictionary()->getChunk(MAX2(n * word_sz, - _dictionary->minSize()), - FreeBlockDictionary::atLeast); + fc = dictionary()->get_chunk(MAX2(n * word_sz, + _dictionary->min_size()), + FreeBlockDictionary::atLeast); if (fc != NULL) { _bt.allocated((HeapWord*)fc, fc->size(), true /* reducing */); // update _unallocated_blk - dictionary()->dictCensusUpdate(fc->size(), + dictionary()->dict_census_udpate(fc->size(), true /*split*/, false /*birth*/); break; @@ -2862,7 +2864,7 @@ if (fc == NULL) return; // Otherwise, split up that block. assert((ssize_t)n >= 1, "Control point invariant"); - assert(fc->isFree(), "Error: should be a free block"); + assert(fc->is_free(), "Error: should be a free block"); _bt.verify_single_block((HeapWord*)fc, fc->size()); const size_t nn = fc->size() / word_sz; n = MIN2(nn, n); @@ -2893,18 +2895,18 @@ if (rem > 0) { size_t prefix_size = n * word_sz; rem_fc = (FreeChunk*)((HeapWord*)fc + prefix_size); - rem_fc->setSize(rem); - rem_fc->linkPrev(NULL); // Mark as a free block for other (parallel) GC threads. - rem_fc->linkNext(NULL); + rem_fc->set_size(rem); + rem_fc->link_prev(NULL); // Mark as a free block for other (parallel) GC threads. + rem_fc->link_next(NULL); // Above must occur before BOT is updated below. assert((ssize_t)n > 0 && prefix_size > 0 && rem_fc > fc, "Error"); OrderAccess::storestore(); _bt.split_block((HeapWord*)fc, fc->size(), prefix_size); - assert(fc->isFree(), "Error"); - fc->setSize(prefix_size); + assert(fc->is_free(), "Error"); + fc->set_size(prefix_size); if (rem >= IndexSetSize) { returnChunkToDictionary(rem_fc); - dictionary()->dictCensusUpdate(rem, true /*split*/, true /*birth*/); + dictionary()->dict_census_udpate(rem, true /*split*/, true /*birth*/); rem_fc = NULL; } // Otherwise, return it to the small list below. @@ -2914,7 +2916,7 @@ MutexLockerEx x(_indexedFreeListParLocks[rem], Mutex::_no_safepoint_check_flag); _bt.verify_not_unallocated((HeapWord*)rem_fc, rem_fc->size()); - _indexedFreeList[rem].returnChunkAtHead(rem_fc); + _indexedFreeList[rem].return_chunk_at_head(rem_fc); smallSplitBirth(rem); } assert((ssize_t)n > 0 && fc != NULL, "Consistency"); @@ -2926,9 +2928,9 @@ // All but first chunk in this loop for (ssize_t i = n-1; i > 0; i--) { FreeChunk* ffc = (FreeChunk*)((HeapWord*)fc + i * word_sz); - ffc->setSize(word_sz); - ffc->linkPrev(NULL); // Mark as a free block for other (parallel) GC threads. - ffc->linkNext(NULL); + ffc->set_size(word_sz); + ffc->link_prev(NULL); // Mark as a free block for other (parallel) GC threads. + ffc->link_next(NULL); // Above must occur before BOT is updated below. OrderAccess::storestore(); // splitting from the right, fc_size == (n - i + 1) * wordsize @@ -2938,25 +2940,25 @@ _bt.verify_single_block((HeapWord*)ffc, ffc->size()); _bt.verify_single_block((HeapWord*)fc, fc_size); // Push this on "fl". - fl->returnChunkAtHead(ffc); + fl->return_chunk_at_head(ffc); } // First chunk - assert(fc->isFree() && fc->size() == n*word_sz, "Error: should still be a free block"); + assert(fc->is_free() && fc->size() == n*word_sz, "Error: should still be a free block"); // The blocks above should show their new sizes before the first block below - fc->setSize(word_sz); - fc->linkPrev(NULL); // idempotent wrt free-ness, see assert above - fc->linkNext(NULL); + fc->set_size(word_sz); + fc->link_prev(NULL); // idempotent wrt free-ness, see assert above + fc->link_next(NULL); _bt.verify_not_unallocated((HeapWord*)fc, fc->size()); _bt.verify_single_block((HeapWord*)fc, fc->size()); - fl->returnChunkAtHead(fc); + fl->return_chunk_at_head(fc); assert((ssize_t)n > 0 && (ssize_t)n == fl->count(), "Incorrect number of blocks"); { // Update the stats for this block size. MutexLockerEx x(_indexedFreeListParLocks[word_sz], Mutex::_no_safepoint_check_flag); - const ssize_t births = _indexedFreeList[word_sz].splitBirths() + n; - _indexedFreeList[word_sz].set_splitBirths(births); + const ssize_t births = _indexedFreeList[word_sz].split_births() + n; + _indexedFreeList[word_sz].set_split_births(births); // ssize_t new_surplus = _indexedFreeList[word_sz].surplus() + n; // _indexedFreeList[word_sz].set_surplus(new_surplus); } diff -r e0d32945f6ab -r fa5227d43363 hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/compactibleFreeListSpace.hpp --- a/hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/compactibleFreeListSpace.hpp Thu May 10 20:05:12 2012 +0400 +++ b/hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/compactibleFreeListSpace.hpp Thu May 10 11:47:56 2012 -0700 @@ -25,10 +25,10 @@ #ifndef SHARE_VM_GC_IMPLEMENTATION_CONCURRENTMARKSWEEP_COMPACTIBLEFREELISTSPACE_HPP #define SHARE_VM_GC_IMPLEMENTATION_CONCURRENTMARKSWEEP_COMPACTIBLEFREELISTSPACE_HPP -#include "gc_implementation/concurrentMarkSweep/binaryTreeDictionary.hpp" -#include "gc_implementation/concurrentMarkSweep/freeList.hpp" #include "gc_implementation/concurrentMarkSweep/promotionInfo.hpp" +#include "memory/binaryTreeDictionary.hpp" #include "memory/blockOffsetTable.inline.hpp" +#include "memory/freeList.hpp" #include "memory/space.hpp" // Classes in support of keeping track of promotions into a non-Contiguous @@ -129,10 +129,10 @@ // Linear allocation blocks LinearAllocBlock _smallLinearAllocBlock; - FreeBlockDictionary::DictionaryChoice _dictionaryChoice; - FreeBlockDictionary* _dictionary; // ptr to dictionary for large size blocks + FreeBlockDictionary::DictionaryChoice _dictionaryChoice; + FreeBlockDictionary* _dictionary; // ptr to dictionary for large size blocks - FreeList _indexedFreeList[IndexSetSize]; + FreeList _indexedFreeList[IndexSetSize]; // indexed array for small size blocks // allocation stategy bool _fitStrategy; // Use best fit strategy. @@ -169,7 +169,7 @@ // If the count of "fl" is negative, it's absolute value indicates a // number of free chunks that had been previously "borrowed" from global // list of size "word_sz", and must now be decremented. - void par_get_chunk_of_blocks(size_t word_sz, size_t n, FreeList* fl); + void par_get_chunk_of_blocks(size_t word_sz, size_t n, FreeList* fl); // Allocation helper functions // Allocate using a strategy that takes from the indexed free lists @@ -215,7 +215,7 @@ // and return it. The split off remainder is returned to // the free lists. The old name for getFromListGreater // was lookInListGreater. - FreeChunk* getFromListGreater(FreeList* fl, size_t numWords); + FreeChunk* getFromListGreater(FreeList* fl, size_t numWords); // Get a chunk in the indexed free list or dictionary, // by considering a larger chunk and splitting it. FreeChunk* getChunkFromGreater(size_t numWords); @@ -286,10 +286,10 @@ // Constructor... CompactibleFreeListSpace(BlockOffsetSharedArray* bs, MemRegion mr, bool use_adaptive_freelists, - FreeBlockDictionary::DictionaryChoice); + FreeBlockDictionary::DictionaryChoice); // accessors bool bestFitFirst() { return _fitStrategy == FreeBlockBestFitFirst; } - FreeBlockDictionary* dictionary() const { return _dictionary; } + FreeBlockDictionary* dictionary() const { return _dictionary; } HeapWord* nearLargestChunk() const { return _nearLargestChunk; } void set_nearLargestChunk(HeapWord* v) { _nearLargestChunk = v; } @@ -499,7 +499,7 @@ // Verify that the given chunk is in the free lists: // i.e. either the binary tree dictionary, the indexed free lists // or the linear allocation block. - bool verifyChunkInFreeLists(FreeChunk* fc) const; + bool verify_chunk_in_free_list(FreeChunk* fc) const; // Verify that the given chunk is the linear allocation block bool verify_chunk_is_linear_alloc_block(FreeChunk* fc) const; // Do some basic checks on the the free lists. @@ -608,7 +608,7 @@ void coalDeath(size_t size); void smallSplitBirth(size_t size); void smallSplitDeath(size_t size); - void splitBirth(size_t size); + void split_birth(size_t size); void splitDeath(size_t size); void split(size_t from, size_t to1); @@ -622,7 +622,7 @@ CompactibleFreeListSpace* _cfls; // Our local free lists. - FreeList _indexedFreeList[CompactibleFreeListSpace::IndexSetSize]; + FreeList _indexedFreeList[CompactibleFreeListSpace::IndexSetSize]; // Initialized from a command-line arg. @@ -635,7 +635,7 @@ size_t _num_blocks [CompactibleFreeListSpace::IndexSetSize]; // Internal work method - void get_from_global_pool(size_t word_sz, FreeList* fl); + void get_from_global_pool(size_t word_sz, FreeList* fl); public: CFLS_LAB(CompactibleFreeListSpace* cfls); diff -r e0d32945f6ab -r fa5227d43363 hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/concurrentMarkSweepGeneration.cpp --- a/hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/concurrentMarkSweepGeneration.cpp Thu May 10 20:05:12 2012 +0400 +++ b/hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/concurrentMarkSweepGeneration.cpp Thu May 10 11:47:56 2012 -0700 @@ -188,7 +188,7 @@ ConcurrentMarkSweepGeneration::ConcurrentMarkSweepGeneration( ReservedSpace rs, size_t initial_byte_size, int level, CardTableRS* ct, bool use_adaptive_freelists, - FreeBlockDictionary::DictionaryChoice dictionaryChoice) : + FreeBlockDictionary::DictionaryChoice dictionaryChoice) : CardGeneration(rs, initial_byte_size, level, ct), _dilatation_factor(((double)MinChunkSize)/((double)(CollectedHeap::min_fill_size()))), _debug_collection_type(Concurrent_collection_type) @@ -1026,7 +1026,7 @@ // its mark-bit or P-bits not yet set. Such objects need // to be safely navigable by block_start(). assert(oop(res)->klass_or_null() == NULL, "Object should be uninitialized here."); - assert(!((FreeChunk*)res)->isFree(), "Error, block will look free but show wrong size"); + assert(!((FreeChunk*)res)->is_free(), "Error, block will look free but show wrong size"); collector()->direct_allocated(res, adjustedSize); _direct_allocated_words += adjustedSize; // allocation counters @@ -1391,7 +1391,7 @@ oop obj = oop(obj_ptr); OrderAccess::storestore(); assert(obj->klass_or_null() == NULL, "Object should be uninitialized here."); - assert(!((FreeChunk*)obj_ptr)->isFree(), "Error, block will look free but show wrong size"); + assert(!((FreeChunk*)obj_ptr)->is_free(), "Error, block will look free but show wrong size"); // IMPORTANT: See note on object initialization for CMS above. // Otherwise, copy the object. Here we must be careful to insert the // klass pointer last, since this marks the block as an allocated object. @@ -1400,7 +1400,7 @@ // Restore the mark word copied above. obj->set_mark(m); assert(obj->klass_or_null() == NULL, "Object should be uninitialized here."); - assert(!((FreeChunk*)obj_ptr)->isFree(), "Error, block will look free but show wrong size"); + assert(!((FreeChunk*)obj_ptr)->is_free(), "Error, block will look free but show wrong size"); OrderAccess::storestore(); if (UseCompressedOops) { @@ -1421,7 +1421,7 @@ promoInfo->track((PromotedObject*)obj, old->klass()); } assert(obj->klass_or_null() == NULL, "Object should be uninitialized here."); - assert(!((FreeChunk*)obj_ptr)->isFree(), "Error, block will look free but show wrong size"); + assert(!((FreeChunk*)obj_ptr)->is_free(), "Error, block will look free but show wrong size"); assert(old->is_oop(), "Will use and dereference old klass ptr below"); // Finally, install the klass pointer (this should be volatile). @@ -2034,7 +2034,7 @@ pointer_delta(cms_space->end(), cms_space->compaction_top()) * HeapWordSize, "All the free space should be compacted into one chunk at top"); - assert(cms_space->dictionary()->totalChunkSize( + assert(cms_space->dictionary()->total_chunk_size( debug_only(cms_space->freelistLock())) == 0 || cms_space->totalSizeInIndexedFreeLists() == 0, "All the free space should be in a single chunk"); @@ -6131,7 +6131,7 @@ double nearLargestPercent = FLSLargestBlockCoalesceProximity; HeapWord* minAddr = _cmsSpace->bottom(); HeapWord* largestAddr = - (HeapWord*) _cmsSpace->dictionary()->findLargestDict(); + (HeapWord*) _cmsSpace->dictionary()->find_largest_dict(); if (largestAddr == NULL) { // The dictionary appears to be empty. In this case // try to coalesce at the end of the heap. @@ -7906,7 +7906,7 @@ _last_fc = NULL; _sp->initializeIndexedFreeListArrayReturnedBytes(); - _sp->dictionary()->initializeDictReturnedBytes(); + _sp->dictionary()->initialize_dict_returned_bytes(); ) assert(_limit >= _sp->bottom() && _limit <= _sp->end(), "sweep _limit out of bounds"); @@ -7954,13 +7954,13 @@ if (PrintCMSStatistics && CMSVerifyReturnedBytes) { size_t indexListReturnedBytes = _sp->sumIndexedFreeListArrayReturnedBytes(); - size_t dictReturnedBytes = _sp->dictionary()->sumDictReturnedBytes(); - size_t returnedBytes = indexListReturnedBytes + dictReturnedBytes; - gclog_or_tty->print("Returned "SIZE_FORMAT" bytes", returnedBytes); + size_t dict_returned_bytes = _sp->dictionary()->sum_dict_returned_bytes(); + size_t returned_bytes = indexListReturnedBytes + dict_returned_bytes; + gclog_or_tty->print("Returned "SIZE_FORMAT" bytes", returned_bytes); gclog_or_tty->print(" Indexed List Returned "SIZE_FORMAT" bytes", indexListReturnedBytes); gclog_or_tty->print_cr(" Dictionary Returned "SIZE_FORMAT" bytes", - dictReturnedBytes); + dict_returned_bytes); } } if (CMSTraceSweeper) { @@ -7985,9 +7985,9 @@ if (CMSTestInFreeList) { if (freeRangeInFreeLists) { FreeChunk* fc = (FreeChunk*) freeFinger; - assert(fc->isFree(), "A chunk on the free list should be free."); + assert(fc->is_free(), "A chunk on the free list should be free."); assert(fc->size() > 0, "Free range should have a size"); - assert(_sp->verifyChunkInFreeLists(fc), "Chunk is not in free lists"); + assert(_sp->verify_chunk_in_free_list(fc), "Chunk is not in free lists"); } } } @@ -8057,7 +8057,7 @@ assert(addr < _limit, "sweep invariant"); // check if we should yield do_yield_check(addr); - if (fc->isFree()) { + if (fc->is_free()) { // Chunk that is already free res = fc->size(); do_already_free_chunk(fc); @@ -8145,7 +8145,7 @@ // Chunks that cannot be coalesced are not in the // free lists. if (CMSTestInFreeList && !fc->cantCoalesce()) { - assert(_sp->verifyChunkInFreeLists(fc), + assert(_sp->verify_chunk_in_free_list(fc), "free chunk should be in free lists"); } // a chunk that is already free, should not have been @@ -8171,7 +8171,7 @@ FreeChunk* nextChunk = (FreeChunk*)(addr + size); assert((HeapWord*)nextChunk <= _sp->end(), "Chunk size out of bounds?"); if ((HeapWord*)nextChunk < _sp->end() && // There is another free chunk to the right ... - nextChunk->isFree() && // ... which is free... + nextChunk->is_free() && // ... which is free... nextChunk->cantCoalesce()) { // ... but can't be coalesced // nothing to do } else { @@ -8203,7 +8203,7 @@ assert(ffc->size() == pointer_delta(addr, freeFinger()), "Size of free range is inconsistent with chunk size."); if (CMSTestInFreeList) { - assert(_sp->verifyChunkInFreeLists(ffc), + assert(_sp->verify_chunk_in_free_list(ffc), "free range is not in free lists"); } _sp->removeFreeChunkFromFreeLists(ffc); @@ -8262,7 +8262,7 @@ assert(ffc->size() == pointer_delta(addr, freeFinger()), "Size of free range is inconsistent with chunk size."); if (CMSTestInFreeList) { - assert(_sp->verifyChunkInFreeLists(ffc), + assert(_sp->verify_chunk_in_free_list(ffc), "free range is not in free lists"); } _sp->removeFreeChunkFromFreeLists(ffc); @@ -8351,11 +8351,11 @@ size_t chunkSize) { // do_post_free_or_garbage_chunk() should only be called in the case // of the adaptive free list allocator. - const bool fcInFreeLists = fc->isFree(); + const bool fcInFreeLists = fc->is_free(); assert(_sp->adaptive_freelists(), "Should only be used in this case."); assert((HeapWord*)fc <= _limit, "sweep invariant"); if (CMSTestInFreeList && fcInFreeLists) { - assert(_sp->verifyChunkInFreeLists(fc), "free chunk is not in free lists"); + assert(_sp->verify_chunk_in_free_list(fc), "free chunk is not in free lists"); } if (CMSTraceSweeper) { @@ -8410,7 +8410,7 @@ assert(ffc->size() == pointer_delta(fc_addr, freeFinger()), "Size of free range is inconsistent with chunk size."); if (CMSTestInFreeList) { - assert(_sp->verifyChunkInFreeLists(ffc), + assert(_sp->verify_chunk_in_free_list(ffc), "Chunk is not in free lists"); } _sp->coalDeath(ffc->size()); @@ -8459,7 +8459,7 @@ " when examining fc = " PTR_FORMAT "(" SIZE_FORMAT ")", _limit, _sp->bottom(), _sp->end(), fc, chunk_size)); if (eob >= _limit) { - assert(eob == _limit || fc->isFree(), "Only a free chunk should allow us to cross over the limit"); + assert(eob == _limit || fc->is_free(), "Only a free chunk should allow us to cross over the limit"); if (CMSTraceSweeper) { gclog_or_tty->print_cr("_limit " PTR_FORMAT " reached or crossed by block " "[" PTR_FORMAT "," PTR_FORMAT ") in space " @@ -8482,8 +8482,8 @@ if (!freeRangeInFreeLists()) { if (CMSTestInFreeList) { FreeChunk* fc = (FreeChunk*) chunk; - fc->setSize(size); - assert(!_sp->verifyChunkInFreeLists(fc), + fc->set_size(size); + assert(!_sp->verify_chunk_in_free_list(fc), "chunk should not be in free lists yet"); } if (CMSTraceSweeper) { @@ -8557,8 +8557,8 @@ // This is actually very useful in a product build if it can // be called from the debugger. Compile it into the product // as needed. -bool debug_verifyChunkInFreeLists(FreeChunk* fc) { - return debug_cms_space->verifyChunkInFreeLists(fc); +bool debug_verify_chunk_in_free_list(FreeChunk* fc) { + return debug_cms_space->verify_chunk_in_free_list(fc); } #endif @@ -9255,7 +9255,7 @@ size_t chunk_at_end_old_size = chunk_at_end->size(); assert(chunk_at_end_old_size >= word_size_change, "Shrink is too large"); - chunk_at_end->setSize(chunk_at_end_old_size - + chunk_at_end->set_size(chunk_at_end_old_size - word_size_change); _cmsSpace->freed((HeapWord*) chunk_at_end->end(), word_size_change); diff -r e0d32945f6ab -r fa5227d43363 hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/concurrentMarkSweepGeneration.hpp --- a/hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/concurrentMarkSweepGeneration.hpp Thu May 10 20:05:12 2012 +0400 +++ b/hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/concurrentMarkSweepGeneration.hpp Thu May 10 11:47:56 2012 -0700 @@ -25,10 +25,10 @@ #ifndef SHARE_VM_GC_IMPLEMENTATION_CONCURRENTMARKSWEEP_CONCURRENTMARKSWEEPGENERATION_HPP #define SHARE_VM_GC_IMPLEMENTATION_CONCURRENTMARKSWEEP_CONCURRENTMARKSWEEPGENERATION_HPP -#include "gc_implementation/concurrentMarkSweep/freeBlockDictionary.hpp" #include "gc_implementation/shared/gSpaceCounters.hpp" #include "gc_implementation/shared/gcStats.hpp" #include "gc_implementation/shared/generationCounters.hpp" +#include "memory/freeBlockDictionary.hpp" #include "memory/generation.hpp" #include "runtime/mutexLocker.hpp" #include "runtime/virtualspace.hpp" @@ -1106,7 +1106,7 @@ ConcurrentMarkSweepGeneration(ReservedSpace rs, size_t initial_byte_size, int level, CardTableRS* ct, bool use_adaptive_freelists, - FreeBlockDictionary::DictionaryChoice); + FreeBlockDictionary::DictionaryChoice); // Accessors CMSCollector* collector() const { return _collector; } @@ -1328,7 +1328,7 @@ ASConcurrentMarkSweepGeneration(ReservedSpace rs, size_t initial_byte_size, int level, CardTableRS* ct, bool use_adaptive_freelists, - FreeBlockDictionary::DictionaryChoice + FreeBlockDictionary::DictionaryChoice dictionaryChoice) : ConcurrentMarkSweepGeneration(rs, initial_byte_size, level, ct, use_adaptive_freelists, dictionaryChoice) {} diff -r e0d32945f6ab -r fa5227d43363 hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/freeBlockDictionary.cpp --- a/hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/freeBlockDictionary.cpp Thu May 10 20:05:12 2012 +0400 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,60 +0,0 @@ -/* - * Copyright (c) 2002, 2010, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - * - */ - -#include "precompiled.hpp" -#include "gc_implementation/concurrentMarkSweep/freeBlockDictionary.hpp" -#ifdef TARGET_OS_FAMILY_linux -# include "thread_linux.inline.hpp" -#endif -#ifdef TARGET_OS_FAMILY_solaris -# include "thread_solaris.inline.hpp" -#endif -#ifdef TARGET_OS_FAMILY_windows -# include "thread_windows.inline.hpp" -#endif -#ifdef TARGET_OS_FAMILY_bsd -# include "thread_bsd.inline.hpp" -#endif - -#ifndef PRODUCT -Mutex* FreeBlockDictionary::par_lock() const { - return _lock; -} - -void FreeBlockDictionary::set_par_lock(Mutex* lock) { - _lock = lock; -} - -void FreeBlockDictionary::verify_par_locked() const { -#ifdef ASSERT - if (ParallelGCThreads > 0) { - Thread* myThread = Thread::current(); - if (myThread->is_GC_task_thread()) { - assert(par_lock() != NULL, "Should be using locking?"); - assert_lock_strong(par_lock()); - } - } -#endif // ASSERT -} -#endif diff -r e0d32945f6ab -r fa5227d43363 hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/freeBlockDictionary.hpp --- a/hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/freeBlockDictionary.hpp Thu May 10 20:05:12 2012 +0400 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,103 +0,0 @@ -/* - * Copyright (c) 2001, 2010, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - * - */ - -#ifndef SHARE_VM_GC_IMPLEMENTATION_CONCURRENTMARKSWEEP_FREEBLOCKDICTIONARY_HPP -#define SHARE_VM_GC_IMPLEMENTATION_CONCURRENTMARKSWEEP_FREEBLOCKDICTIONARY_HPP - -#include "gc_implementation/concurrentMarkSweep/freeChunk.hpp" -#include "memory/allocation.hpp" -#include "memory/memRegion.hpp" -#include "runtime/mutex.hpp" -#include "utilities/debug.hpp" -#include "utilities/globalDefinitions.hpp" -#include "utilities/ostream.hpp" - -// A FreeBlockDictionary is an abstract superclass that will allow -// a number of alternative implementations in the future. -class FreeBlockDictionary: public CHeapObj { - public: - enum Dither { - atLeast, - exactly, - roughly - }; - enum DictionaryChoice { - dictionaryBinaryTree = 0, - dictionarySplayTree = 1, - dictionarySkipList = 2 - }; - - private: - NOT_PRODUCT(Mutex* _lock;) - - public: - virtual void removeChunk(FreeChunk* fc) = 0; - virtual FreeChunk* getChunk(size_t size, Dither dither = atLeast) = 0; - virtual void returnChunk(FreeChunk* chunk) = 0; - virtual size_t totalChunkSize(debug_only(const Mutex* lock)) const = 0; - virtual size_t maxChunkSize() const = 0; - virtual size_t minSize() const = 0; - // Reset the dictionary to the initial conditions for a single - // block. - virtual void reset(HeapWord* addr, size_t size) = 0; - virtual void reset() = 0; - - virtual void dictCensusUpdate(size_t size, bool split, bool birth) = 0; - virtual bool coalDictOverPopulated(size_t size) = 0; - virtual void beginSweepDictCensus(double coalSurplusPercent, - float inter_sweep_current, float inter_sweep_estimate, - float intra__sweep_current) = 0; - virtual void endSweepDictCensus(double splitSurplusPercent) = 0; - virtual FreeChunk* findLargestDict() const = 0; - // verify that the given chunk is in the dictionary. - virtual bool verifyChunkInFreeLists(FreeChunk* tc) const = 0; - - // Sigma_{all_free_blocks} (block_size^2) - virtual double sum_of_squared_block_sizes() const = 0; - - virtual FreeChunk* find_chunk_ends_at(HeapWord* target) const = 0; - virtual void inc_totalSize(size_t v) = 0; - virtual void dec_totalSize(size_t v) = 0; - - NOT_PRODUCT ( - virtual size_t sumDictReturnedBytes() = 0; - virtual void initializeDictReturnedBytes() = 0; - virtual size_t totalCount() = 0; - ) - - virtual void reportStatistics() const { - gclog_or_tty->print("No statistics available"); - } - - virtual void printDictCensus() const = 0; - virtual void print_free_lists(outputStream* st) const = 0; - - virtual void verify() const = 0; - - Mutex* par_lock() const PRODUCT_RETURN0; - void set_par_lock(Mutex* lock) PRODUCT_RETURN; - void verify_par_locked() const PRODUCT_RETURN; -}; - -#endif // SHARE_VM_GC_IMPLEMENTATION_CONCURRENTMARKSWEEP_FREEBLOCKDICTIONARY_HPP diff -r e0d32945f6ab -r fa5227d43363 hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/freeChunk.cpp --- a/hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/freeChunk.cpp Thu May 10 20:05:12 2012 +0400 +++ b/hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/freeChunk.cpp Thu May 10 11:47:56 2012 -0700 @@ -23,7 +23,8 @@ */ #include "precompiled.hpp" -#include "gc_implementation/concurrentMarkSweep/freeBlockDictionary.hpp" +#include "gc_implementation/concurrentMarkSweep/freeChunk.hpp" +#include "memory/freeBlockDictionary.hpp" #include "utilities/copy.hpp" #ifndef PRODUCT diff -r e0d32945f6ab -r fa5227d43363 hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/freeChunk.hpp --- a/hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/freeChunk.hpp Thu May 10 20:05:12 2012 +0400 +++ b/hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/freeChunk.hpp Thu May 10 11:47:56 2012 -0700 @@ -75,20 +75,20 @@ // calls. We really want the read of _mark and _prev from this pointer // to be volatile but making the fields volatile causes all sorts of // compilation errors. - return ((volatile FreeChunk*)addr)->isFree(); + return ((volatile FreeChunk*)addr)->is_free(); } - bool isFree() const volatile { + bool is_free() const volatile { LP64_ONLY(if (UseCompressedOops) return mark()->is_cms_free_chunk(); else) return (((intptr_t)_prev) & 0x1) == 0x1; } bool cantCoalesce() const { - assert(isFree(), "can't get coalesce bit on not free"); + assert(is_free(), "can't get coalesce bit on not free"); return (((intptr_t)_prev) & 0x2) == 0x2; } void dontCoalesce() { // the block should be free - assert(isFree(), "Should look like a free block"); + assert(is_free(), "Should look like a free block"); _prev = (FreeChunk*)(((intptr_t)_prev) | 0x2); } FreeChunk* prev() const { @@ -103,23 +103,23 @@ LP64_ONLY(if (UseCompressedOops) return mark()->get_size(); else ) return _size; } - void setSize(size_t sz) { + void set_size(size_t sz) { LP64_ONLY(if (UseCompressedOops) set_mark(markOopDesc::set_size_and_free(sz)); else ) _size = sz; } FreeChunk* next() const { return _next; } - void linkAfter(FreeChunk* ptr) { - linkNext(ptr); - if (ptr != NULL) ptr->linkPrev(this); + void link_after(FreeChunk* ptr) { + link_next(ptr); + if (ptr != NULL) ptr->link_prev(this); } - void linkNext(FreeChunk* ptr) { _next = ptr; } - void linkPrev(FreeChunk* ptr) { + void link_next(FreeChunk* ptr) { _next = ptr; } + void link_prev(FreeChunk* ptr) { LP64_ONLY(if (UseCompressedOops) _prev = ptr; else) _prev = (FreeChunk*)((intptr_t)ptr | 0x1); } - void clearNext() { _next = NULL; } + void clear_next() { _next = NULL; } void markNotFree() { // Set _prev (klass) to null before (if) clearing the mark word below _prev = NULL; @@ -129,7 +129,7 @@ set_mark(markOopDesc::prototype()); } #endif - assert(!isFree(), "Error"); + assert(!is_free(), "Error"); } // Return the address past the end of this chunk diff -r e0d32945f6ab -r fa5227d43363 hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/freeList.cpp --- a/hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/freeList.cpp Thu May 10 20:05:12 2012 +0400 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,360 +0,0 @@ -/* - * Copyright (c) 2001, 2010, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - * - */ - -#include "precompiled.hpp" -#include "gc_implementation/concurrentMarkSweep/freeBlockDictionary.hpp" -#include "gc_implementation/concurrentMarkSweep/freeList.hpp" -#include "memory/sharedHeap.hpp" -#include "runtime/globals.hpp" -#include "runtime/mutex.hpp" -#include "runtime/vmThread.hpp" - -// Free list. A FreeList is used to access a linked list of chunks -// of space in the heap. The head and tail are maintained so that -// items can be (as in the current implementation) added at the -// at the tail of the list and removed from the head of the list to -// maintain a FIFO queue. - -FreeList::FreeList() : - _head(NULL), _tail(NULL) -#ifdef ASSERT - , _protecting_lock(NULL) -#endif -{ - _size = 0; - _count = 0; - _hint = 0; - init_statistics(); -} - -FreeList::FreeList(FreeChunk* fc) : - _head(fc), _tail(fc) -#ifdef ASSERT - , _protecting_lock(NULL) -#endif -{ - _size = fc->size(); - _count = 1; - _hint = 0; - init_statistics(); -#ifndef PRODUCT - _allocation_stats.set_returnedBytes(size() * HeapWordSize); -#endif -} - -FreeList::FreeList(HeapWord* addr, size_t size) : - _head((FreeChunk*) addr), _tail((FreeChunk*) addr) -#ifdef ASSERT - , _protecting_lock(NULL) -#endif -{ - assert(size > sizeof(FreeChunk), "size is too small"); - head()->setSize(size); - _size = size; - _count = 1; - init_statistics(); -#ifndef PRODUCT - _allocation_stats.set_returnedBytes(_size * HeapWordSize); -#endif -} - -void FreeList::reset(size_t hint) { - set_count(0); - set_head(NULL); - set_tail(NULL); - set_hint(hint); -} - -void FreeList::init_statistics(bool split_birth) { - _allocation_stats.initialize(split_birth); -} - -FreeChunk* FreeList::getChunkAtHead() { - assert_proper_lock_protection(); - assert(head() == NULL || head()->prev() == NULL, "list invariant"); - assert(tail() == NULL || tail()->next() == NULL, "list invariant"); - FreeChunk* fc = head(); - if (fc != NULL) { - FreeChunk* nextFC = fc->next(); - if (nextFC != NULL) { - // The chunk fc being removed has a "next". Set the "next" to the - // "prev" of fc. - nextFC->linkPrev(NULL); - } else { // removed tail of list - link_tail(NULL); - } - link_head(nextFC); - decrement_count(); - } - assert(head() == NULL || head()->prev() == NULL, "list invariant"); - assert(tail() == NULL || tail()->next() == NULL, "list invariant"); - return fc; -} - - -void FreeList::getFirstNChunksFromList(size_t n, FreeList* fl) { - assert_proper_lock_protection(); - assert(fl->count() == 0, "Precondition"); - if (count() > 0) { - int k = 1; - fl->set_head(head()); n--; - FreeChunk* tl = head(); - while (tl->next() != NULL && n > 0) { - tl = tl->next(); n--; k++; - } - assert(tl != NULL, "Loop Inv."); - - // First, fix up the list we took from. - FreeChunk* new_head = tl->next(); - set_head(new_head); - set_count(count() - k); - if (new_head == NULL) { - set_tail(NULL); - } else { - new_head->linkPrev(NULL); - } - // Now we can fix up the tail. - tl->linkNext(NULL); - // And return the result. - fl->set_tail(tl); - fl->set_count(k); - } -} - -// Remove this chunk from the list -void FreeList::removeChunk(FreeChunk*fc) { - assert_proper_lock_protection(); - assert(head() != NULL, "Remove from empty list"); - assert(fc != NULL, "Remove a NULL chunk"); - assert(size() == fc->size(), "Wrong list"); - assert(head() == NULL || head()->prev() == NULL, "list invariant"); - assert(tail() == NULL || tail()->next() == NULL, "list invariant"); - - FreeChunk* prevFC = fc->prev(); - FreeChunk* nextFC = fc->next(); - if (nextFC != NULL) { - // The chunk fc being removed has a "next". Set the "next" to the - // "prev" of fc. - nextFC->linkPrev(prevFC); - } else { // removed tail of list - link_tail(prevFC); - } - if (prevFC == NULL) { // removed head of list - link_head(nextFC); - assert(nextFC == NULL || nextFC->prev() == NULL, - "Prev of head should be NULL"); - } else { - prevFC->linkNext(nextFC); - assert(tail() != prevFC || prevFC->next() == NULL, - "Next of tail should be NULL"); - } - decrement_count(); - assert(((head() == NULL) + (tail() == NULL) + (count() == 0)) % 3 == 0, - "H/T/C Inconsistency"); - // clear next and prev fields of fc, debug only - NOT_PRODUCT( - fc->linkPrev(NULL); - fc->linkNext(NULL); - ) - assert(fc->isFree(), "Should still be a free chunk"); - assert(head() == NULL || head()->prev() == NULL, "list invariant"); - assert(tail() == NULL || tail()->next() == NULL, "list invariant"); - assert(head() == NULL || head()->size() == size(), "wrong item on list"); - assert(tail() == NULL || tail()->size() == size(), "wrong item on list"); -} - -// Add this chunk at the head of the list. -void FreeList::returnChunkAtHead(FreeChunk* chunk, bool record_return) { - assert_proper_lock_protection(); - assert(chunk != NULL, "insert a NULL chunk"); - assert(size() == chunk->size(), "Wrong size"); - assert(head() == NULL || head()->prev() == NULL, "list invariant"); - assert(tail() == NULL || tail()->next() == NULL, "list invariant"); - - FreeChunk* oldHead = head(); - assert(chunk != oldHead, "double insertion"); - chunk->linkAfter(oldHead); - link_head(chunk); - if (oldHead == NULL) { // only chunk in list - assert(tail() == NULL, "inconsistent FreeList"); - link_tail(chunk); - } - increment_count(); // of # of chunks in list - DEBUG_ONLY( - if (record_return) { - increment_returnedBytes_by(size()*HeapWordSize); - } - ) - assert(head() == NULL || head()->prev() == NULL, "list invariant"); - assert(tail() == NULL || tail()->next() == NULL, "list invariant"); - assert(head() == NULL || head()->size() == size(), "wrong item on list"); - assert(tail() == NULL || tail()->size() == size(), "wrong item on list"); -} - -void FreeList::returnChunkAtHead(FreeChunk* chunk) { - assert_proper_lock_protection(); - returnChunkAtHead(chunk, true); -} - -// Add this chunk at the tail of the list. -void FreeList::returnChunkAtTail(FreeChunk* chunk, bool record_return) { - assert_proper_lock_protection(); - assert(head() == NULL || head()->prev() == NULL, "list invariant"); - assert(tail() == NULL || tail()->next() == NULL, "list invariant"); - assert(chunk != NULL, "insert a NULL chunk"); - assert(size() == chunk->size(), "wrong size"); - - FreeChunk* oldTail = tail(); - assert(chunk != oldTail, "double insertion"); - if (oldTail != NULL) { - oldTail->linkAfter(chunk); - } else { // only chunk in list - assert(head() == NULL, "inconsistent FreeList"); - link_head(chunk); - } - link_tail(chunk); - increment_count(); // of # of chunks in list - DEBUG_ONLY( - if (record_return) { - increment_returnedBytes_by(size()*HeapWordSize); - } - ) - assert(head() == NULL || head()->prev() == NULL, "list invariant"); - assert(tail() == NULL || tail()->next() == NULL, "list invariant"); - assert(head() == NULL || head()->size() == size(), "wrong item on list"); - assert(tail() == NULL || tail()->size() == size(), "wrong item on list"); -} - -void FreeList::returnChunkAtTail(FreeChunk* chunk) { - returnChunkAtTail(chunk, true); -} - -void FreeList::prepend(FreeList* fl) { - assert_proper_lock_protection(); - if (fl->count() > 0) { - if (count() == 0) { - set_head(fl->head()); - set_tail(fl->tail()); - set_count(fl->count()); - } else { - // Both are non-empty. - FreeChunk* fl_tail = fl->tail(); - FreeChunk* this_head = head(); - assert(fl_tail->next() == NULL, "Well-formedness of fl"); - fl_tail->linkNext(this_head); - this_head->linkPrev(fl_tail); - set_head(fl->head()); - set_count(count() + fl->count()); - } - fl->set_head(NULL); - fl->set_tail(NULL); - fl->set_count(0); - } -} - -// verifyChunkInFreeLists() is used to verify that an item is in this free list. -// It is used as a debugging aid. -bool FreeList::verifyChunkInFreeLists(FreeChunk* fc) const { - // This is an internal consistency check, not part of the check that the - // chunk is in the free lists. - guarantee(fc->size() == size(), "Wrong list is being searched"); - FreeChunk* curFC = head(); - while (curFC) { - // This is an internal consistency check. - guarantee(size() == curFC->size(), "Chunk is in wrong list."); - if (fc == curFC) { - return true; - } - curFC = curFC->next(); - } - return false; -} - -#ifndef PRODUCT -void FreeList::verify_stats() const { - // The +1 of the LH comparand is to allow some "looseness" in - // checking: we usually call this interface when adding a block - // and we'll subsequently update the stats; we cannot update the - // stats beforehand because in the case of the large-block BT - // dictionary for example, this might be the first block and - // in that case there would be no place that we could record - // the stats (which are kept in the block itself). - assert((_allocation_stats.prevSweep() + _allocation_stats.splitBirths() - + _allocation_stats.coalBirths() + 1) // Total Production Stock + 1 - >= (_allocation_stats.splitDeaths() + _allocation_stats.coalDeaths() - + (ssize_t)count()), // Total Current Stock + depletion - err_msg("FreeList " PTR_FORMAT " of size " SIZE_FORMAT - " violates Conservation Principle: " - "prevSweep(" SIZE_FORMAT ")" - " + splitBirths(" SIZE_FORMAT ")" - " + coalBirths(" SIZE_FORMAT ") + 1 >= " - " splitDeaths(" SIZE_FORMAT ")" - " coalDeaths(" SIZE_FORMAT ")" - " + count(" SSIZE_FORMAT ")", - this, _size, _allocation_stats.prevSweep(), _allocation_stats.splitBirths(), - _allocation_stats.splitBirths(), _allocation_stats.splitDeaths(), - _allocation_stats.coalDeaths(), count())); -} - -void FreeList::assert_proper_lock_protection_work() const { - assert(_protecting_lock != NULL, "Don't call this directly"); - assert(ParallelGCThreads > 0, "Don't call this directly"); - Thread* thr = Thread::current(); - if (thr->is_VM_thread() || thr->is_ConcurrentGC_thread()) { - // assert that we are holding the freelist lock - } else if (thr->is_GC_task_thread()) { - assert(_protecting_lock->owned_by_self(), "FreeList RACE DETECTED"); - } else if (thr->is_Java_thread()) { - assert(!SafepointSynchronize::is_at_safepoint(), "Should not be executing"); - } else { - ShouldNotReachHere(); // unaccounted thread type? - } -} -#endif - -// Print the "label line" for free list stats. -void FreeList::print_labels_on(outputStream* st, const char* c) { - st->print("%16s\t", c); - st->print("%14s\t" "%14s\t" "%14s\t" "%14s\t" "%14s\t" - "%14s\t" "%14s\t" "%14s\t" "%14s\t" "%14s\t" "\n", - "bfrsurp", "surplus", "desired", "prvSwep", "bfrSwep", - "count", "cBirths", "cDeaths", "sBirths", "sDeaths"); -} - -// Print the AllocationStats for the given free list. If the second argument -// to the call is a non-null string, it is printed in the first column; -// otherwise, if the argument is null (the default), then the size of the -// (free list) block is printed in the first column. -void FreeList::print_on(outputStream* st, const char* c) const { - if (c != NULL) { - st->print("%16s", c); - } else { - st->print(SIZE_FORMAT_W(16), size()); - } - st->print("\t" - SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" - SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\n", - bfrSurp(), surplus(), desired(), prevSweep(), beforeSweep(), - count(), coalBirths(), coalDeaths(), splitBirths(), splitDeaths()); -} diff -r e0d32945f6ab -r fa5227d43363 hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/freeList.hpp --- a/hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/freeList.hpp Thu May 10 20:05:12 2012 +0400 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,335 +0,0 @@ -/* - * Copyright (c) 2001, 2010, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - * - */ - -#ifndef SHARE_VM_GC_IMPLEMENTATION_CONCURRENTMARKSWEEP_FREELIST_HPP -#define SHARE_VM_GC_IMPLEMENTATION_CONCURRENTMARKSWEEP_FREELIST_HPP - -#include "gc_implementation/shared/allocationStats.hpp" - -class CompactibleFreeListSpace; - -// A class for maintaining a free list of FreeChunk's. The FreeList -// maintains a the structure of the list (head, tail, etc.) plus -// statistics for allocations from the list. The links between items -// are not part of FreeList. The statistics are -// used to make decisions about coalescing FreeChunk's when they -// are swept during collection. -// -// See the corresponding .cpp file for a description of the specifics -// for that implementation. - -class Mutex; -class TreeList; - -class FreeList VALUE_OBJ_CLASS_SPEC { - friend class CompactibleFreeListSpace; - friend class VMStructs; - friend class PrintTreeCensusClosure; - - protected: - TreeList* _parent; - TreeList* _left; - TreeList* _right; - - private: - FreeChunk* _head; // Head of list of free chunks - FreeChunk* _tail; // Tail of list of free chunks - size_t _size; // Size in Heap words of each chunk - ssize_t _count; // Number of entries in list - size_t _hint; // next larger size list with a positive surplus - - AllocationStats _allocation_stats; // allocation-related statistics - -#ifdef ASSERT - Mutex* _protecting_lock; -#endif - - // Asserts false if the protecting lock (if any) is not held. - void assert_proper_lock_protection_work() const PRODUCT_RETURN; - void assert_proper_lock_protection() const { -#ifdef ASSERT - if (_protecting_lock != NULL) - assert_proper_lock_protection_work(); -#endif - } - - // Initialize the allocation statistics. - protected: - void init_statistics(bool split_birth = false); - void set_count(ssize_t v) { _count = v;} - void increment_count() { - _count++; - } - - void decrement_count() { - _count--; - assert(_count >= 0, "Count should not be negative"); - } - - public: - // Constructor - // Construct a list without any entries. - FreeList(); - // Construct a list with "fc" as the first (and lone) entry in the list. - FreeList(FreeChunk* fc); - // Construct a list which will have a FreeChunk at address "addr" and - // of size "size" as the first (and lone) entry in the list. - FreeList(HeapWord* addr, size_t size); - - // Reset the head, tail, hint, and count of a free list. - void reset(size_t hint); - - // Declare the current free list to be protected by the given lock. -#ifdef ASSERT - void set_protecting_lock(Mutex* protecting_lock) { - _protecting_lock = protecting_lock; - } -#endif - - // Accessors. - FreeChunk* head() const { - assert_proper_lock_protection(); - return _head; - } - void set_head(FreeChunk* v) { - assert_proper_lock_protection(); - _head = v; - assert(!_head || _head->size() == _size, "bad chunk size"); - } - // Set the head of the list and set the prev field of non-null - // values to NULL. - void link_head(FreeChunk* v) { - assert_proper_lock_protection(); - set_head(v); - // If this method is not used (just set the head instead), - // this check can be avoided. - if (v != NULL) { - v->linkPrev(NULL); - } - } - - FreeChunk* tail() const { - assert_proper_lock_protection(); - return _tail; - } - void set_tail(FreeChunk* v) { - assert_proper_lock_protection(); - _tail = v; - assert(!_tail || _tail->size() == _size, "bad chunk size"); - } - // Set the tail of the list and set the next field of non-null - // values to NULL. - void link_tail(FreeChunk* v) { - assert_proper_lock_protection(); - set_tail(v); - if (v != NULL) { - v->clearNext(); - } - } - - // No locking checks in read-accessors: lock-free reads (only) are benign. - // Readers are expected to have the lock if they are doing work that - // requires atomicity guarantees in sections of code. - size_t size() const { - return _size; - } - void set_size(size_t v) { - assert_proper_lock_protection(); - _size = v; - } - ssize_t count() const { - return _count; - } - size_t hint() const { - return _hint; - } - void set_hint(size_t v) { - assert_proper_lock_protection(); - assert(v == 0 || _size < v, "Bad hint"); _hint = v; - } - - // Accessors for statistics - AllocationStats* allocation_stats() { - assert_proper_lock_protection(); - return &_allocation_stats; - } - - ssize_t desired() const { - return _allocation_stats.desired(); - } - void set_desired(ssize_t v) { - assert_proper_lock_protection(); - _allocation_stats.set_desired(v); - } - void compute_desired(float inter_sweep_current, - float inter_sweep_estimate, - float intra_sweep_estimate) { - assert_proper_lock_protection(); - _allocation_stats.compute_desired(_count, - inter_sweep_current, - inter_sweep_estimate, - intra_sweep_estimate); - } - ssize_t coalDesired() const { - return _allocation_stats.coalDesired(); - } - void set_coalDesired(ssize_t v) { - assert_proper_lock_protection(); - _allocation_stats.set_coalDesired(v); - } - - ssize_t surplus() const { - return _allocation_stats.surplus(); - } - void set_surplus(ssize_t v) { - assert_proper_lock_protection(); - _allocation_stats.set_surplus(v); - } - void increment_surplus() { - assert_proper_lock_protection(); - _allocation_stats.increment_surplus(); - } - void decrement_surplus() { - assert_proper_lock_protection(); - _allocation_stats.decrement_surplus(); - } - - ssize_t bfrSurp() const { - return _allocation_stats.bfrSurp(); - } - void set_bfrSurp(ssize_t v) { - assert_proper_lock_protection(); - _allocation_stats.set_bfrSurp(v); - } - ssize_t prevSweep() const { - return _allocation_stats.prevSweep(); - } - void set_prevSweep(ssize_t v) { - assert_proper_lock_protection(); - _allocation_stats.set_prevSweep(v); - } - ssize_t beforeSweep() const { - return _allocation_stats.beforeSweep(); - } - void set_beforeSweep(ssize_t v) { - assert_proper_lock_protection(); - _allocation_stats.set_beforeSweep(v); - } - - ssize_t coalBirths() const { - return _allocation_stats.coalBirths(); - } - void set_coalBirths(ssize_t v) { - assert_proper_lock_protection(); - _allocation_stats.set_coalBirths(v); - } - void increment_coalBirths() { - assert_proper_lock_protection(); - _allocation_stats.increment_coalBirths(); - } - - ssize_t coalDeaths() const { - return _allocation_stats.coalDeaths(); - } - void set_coalDeaths(ssize_t v) { - assert_proper_lock_protection(); - _allocation_stats.set_coalDeaths(v); - } - void increment_coalDeaths() { - assert_proper_lock_protection(); - _allocation_stats.increment_coalDeaths(); - } - - ssize_t splitBirths() const { - return _allocation_stats.splitBirths(); - } - void set_splitBirths(ssize_t v) { - assert_proper_lock_protection(); - _allocation_stats.set_splitBirths(v); - } - void increment_splitBirths() { - assert_proper_lock_protection(); - _allocation_stats.increment_splitBirths(); - } - - ssize_t splitDeaths() const { - return _allocation_stats.splitDeaths(); - } - void set_splitDeaths(ssize_t v) { - assert_proper_lock_protection(); - _allocation_stats.set_splitDeaths(v); - } - void increment_splitDeaths() { - assert_proper_lock_protection(); - _allocation_stats.increment_splitDeaths(); - } - - NOT_PRODUCT( - // For debugging. The "_returnedBytes" in all the lists are summed - // and compared with the total number of bytes swept during a - // collection. - size_t returnedBytes() const { return _allocation_stats.returnedBytes(); } - void set_returnedBytes(size_t v) { _allocation_stats.set_returnedBytes(v); } - void increment_returnedBytes_by(size_t v) { - _allocation_stats.set_returnedBytes(_allocation_stats.returnedBytes() + v); - } - ) - - // Unlink head of list and return it. Returns NULL if - // the list is empty. - FreeChunk* getChunkAtHead(); - - // Remove the first "n" or "count", whichever is smaller, chunks from the - // list, setting "fl", which is required to be empty, to point to them. - void getFirstNChunksFromList(size_t n, FreeList* fl); - - // Unlink this chunk from it's free list - void removeChunk(FreeChunk* fc); - - // Add this chunk to this free list. - void returnChunkAtHead(FreeChunk* fc); - void returnChunkAtTail(FreeChunk* fc); - - // Similar to returnChunk* but also records some diagnostic - // information. - void returnChunkAtHead(FreeChunk* fc, bool record_return); - void returnChunkAtTail(FreeChunk* fc, bool record_return); - - // Prepend "fl" (whose size is required to be the same as that of "this") - // to the front of "this" list. - void prepend(FreeList* fl); - - // Verify that the chunk is in the list. - // found. Return NULL if "fc" is not found. - bool verifyChunkInFreeLists(FreeChunk* fc) const; - - // Stats verification - void verify_stats() const PRODUCT_RETURN; - - // Printing support - static void print_labels_on(outputStream* st, const char* c); - void print_on(outputStream* st, const char* c = NULL) const; -}; - -#endif // SHARE_VM_GC_IMPLEMENTATION_CONCURRENTMARKSWEEP_FREELIST_HPP diff -r e0d32945f6ab -r fa5227d43363 hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/promotionInfo.cpp --- a/hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/promotionInfo.cpp Thu May 10 20:05:12 2012 +0400 +++ b/hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/promotionInfo.cpp Thu May 10 11:47:56 2012 -0700 @@ -121,7 +121,7 @@ void PromotionInfo::track(PromotedObject* trackOop, klassOop klassOfOop) { // make a copy of header as it may need to be spooled markOop mark = oop(trackOop)->mark(); - trackOop->clearNext(); + trackOop->clear_next(); if (mark->must_be_preserved_for_cms_scavenge(klassOfOop)) { // save non-prototypical header, and mark oop saveDisplacedHeader(mark); diff -r e0d32945f6ab -r fa5227d43363 hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/promotionInfo.hpp --- a/hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/promotionInfo.hpp Thu May 10 20:05:12 2012 +0400 +++ b/hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/promotionInfo.hpp Thu May 10 11:47:56 2012 -0700 @@ -43,7 +43,7 @@ // whose position will depend on endian-ness of the platform. // This is so that there is no interference with the // cms_free_bit occupying bit position 7 (lsb == 0) - // when we are using compressed oops; see FreeChunk::isFree(). + // when we are using compressed oops; see FreeChunk::is_free(). // We cannot move the cms_free_bit down because currently // biased locking code assumes that age bits are contiguous // with the lock bits. Even if that assumption were relaxed, @@ -65,7 +65,7 @@ }; public: inline PromotedObject* next() const { - assert(!((FreeChunk*)this)->isFree(), "Error"); + assert(!((FreeChunk*)this)->is_free(), "Error"); PromotedObject* res; if (UseCompressedOops) { // The next pointer is a compressed oop stored in the top 32 bits @@ -85,27 +85,27 @@ } else { _next |= (intptr_t)x; } - assert(!((FreeChunk*)this)->isFree(), "Error"); + assert(!((FreeChunk*)this)->is_free(), "Error"); } inline void setPromotedMark() { _next |= promoted_mask; - assert(!((FreeChunk*)this)->isFree(), "Error"); + assert(!((FreeChunk*)this)->is_free(), "Error"); } inline bool hasPromotedMark() const { - assert(!((FreeChunk*)this)->isFree(), "Error"); + assert(!((FreeChunk*)this)->is_free(), "Error"); return (_next & promoted_mask) == promoted_mask; } inline void setDisplacedMark() { _next |= displaced_mark; - assert(!((FreeChunk*)this)->isFree(), "Error"); + assert(!((FreeChunk*)this)->is_free(), "Error"); } inline bool hasDisplacedMark() const { - assert(!((FreeChunk*)this)->isFree(), "Error"); + assert(!((FreeChunk*)this)->is_free(), "Error"); return (_next & displaced_mark) != 0; } - inline void clearNext() { + inline void clear_next() { _next = 0; - assert(!((FreeChunk*)this)->isFree(), "Error"); + assert(!((FreeChunk*)this)->is_free(), "Error"); } debug_only(void *next_addr() { return (void *) &_next; }) }; diff -r e0d32945f6ab -r fa5227d43363 hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/vmStructs_cms.hpp --- a/hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/vmStructs_cms.hpp Thu May 10 20:05:12 2012 +0400 +++ b/hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/vmStructs_cms.hpp Thu May 10 11:47:56 2012 -0700 @@ -44,11 +44,11 @@ nonstatic_field(FreeChunk, _next, FreeChunk*) \ nonstatic_field(FreeChunk, _prev, FreeChunk*) \ nonstatic_field(LinearAllocBlock, _word_size, size_t) \ - nonstatic_field(FreeList, _size, size_t) \ - nonstatic_field(FreeList, _count, ssize_t) \ - nonstatic_field(BinaryTreeDictionary, _totalSize, size_t) \ - nonstatic_field(CompactibleFreeListSpace, _dictionary, FreeBlockDictionary*) \ - nonstatic_field(CompactibleFreeListSpace, _indexedFreeList[0], FreeList) \ + nonstatic_field(FreeList, _size, size_t) \ + nonstatic_field(FreeList, _count, ssize_t) \ + nonstatic_field(BinaryTreeDictionary,_total_size, size_t) \ + nonstatic_field(CompactibleFreeListSpace, _dictionary, FreeBlockDictionary*) \ + nonstatic_field(CompactibleFreeListSpace, _indexedFreeList[0], FreeList) \ nonstatic_field(CompactibleFreeListSpace, _smallLinearAllocBlock, LinearAllocBlock) @@ -70,13 +70,13 @@ declare_toplevel_type(CompactibleFreeListSpace*) \ declare_toplevel_type(CMSCollector*) \ declare_toplevel_type(FreeChunk*) \ - declare_toplevel_type(BinaryTreeDictionary*) \ - declare_toplevel_type(FreeBlockDictionary*) \ - declare_toplevel_type(FreeList*) \ - declare_toplevel_type(FreeList) \ + declare_toplevel_type(BinaryTreeDictionary*) \ + declare_toplevel_type(FreeBlockDictionary*) \ + declare_toplevel_type(FreeList*) \ + declare_toplevel_type(FreeList) \ declare_toplevel_type(LinearAllocBlock) \ - declare_toplevel_type(FreeBlockDictionary) \ - declare_type(BinaryTreeDictionary, FreeBlockDictionary) + declare_toplevel_type(FreeBlockDictionary) \ + declare_type(BinaryTreeDictionary, FreeBlockDictionary) #define VM_INT_CONSTANTS_CMS(declare_constant) \ declare_constant(Generation::ConcurrentMarkSweep) \ diff -r e0d32945f6ab -r fa5227d43363 hotspot/src/share/vm/gc_implementation/g1/concurrentMark.cpp --- a/hotspot/src/share/vm/gc_implementation/g1/concurrentMark.cpp Thu May 10 20:05:12 2012 +0400 +++ b/hotspot/src/share/vm/gc_implementation/g1/concurrentMark.cpp Thu May 10 11:47:56 2012 -0700 @@ -1183,35 +1183,31 @@ g1p->record_concurrent_mark_remark_end(); } -// Used to calculate the # live objects per region -// for verification purposes -class CalcLiveObjectsClosure: public HeapRegionClosure { - - CMBitMapRO* _bm; +// Base class of the closures that finalize and verify the +// liveness counting data. +class CMCountDataClosureBase: public HeapRegionClosure { +protected: ConcurrentMark* _cm; BitMap* _region_bm; BitMap* _card_bm; - size_t _region_marked_bytes; - - intptr_t _bottom_card_num; - - void mark_card_num_range(intptr_t start_card_num, intptr_t last_card_num) { - assert(start_card_num <= last_card_num, "sanity"); - BitMap::idx_t start_idx = start_card_num - _bottom_card_num; - BitMap::idx_t last_idx = last_card_num - _bottom_card_num; - - for (BitMap::idx_t i = start_idx; i <= last_idx; i += 1) { - _card_bm->par_at_put(i, 1); + void set_card_bitmap_range(BitMap::idx_t start_idx, BitMap::idx_t last_idx) { + assert(start_idx <= last_idx, "sanity"); + + // Set the inclusive bit range [start_idx, last_idx]. + // For small ranges (up to 8 cards) use a simple loop; otherwise + // use par_at_put_range. + if ((last_idx - start_idx) < 8) { + for (BitMap::idx_t i = start_idx; i <= last_idx; i += 1) { + _card_bm->par_set_bit(i); + } + } else { + assert(last_idx < _card_bm->size(), "sanity"); + // Note BitMap::par_at_put_range() is exclusive. + _card_bm->par_at_put_range(start_idx, last_idx+1, true); } } -public: - CalcLiveObjectsClosure(CMBitMapRO *bm, ConcurrentMark *cm, - BitMap* region_bm, BitMap* card_bm) : - _bm(bm), _cm(cm), _region_bm(region_bm), _card_bm(card_bm), - _region_marked_bytes(0), _bottom_card_num(cm->heap_bottom_card_num()) { } - // It takes a region that's not empty (i.e., it has at least one // live object in it and sets its corresponding bit on the region // bitmap to 1. If the region is "starts humongous" it will also set @@ -1234,6 +1230,24 @@ } } +public: + CMCountDataClosureBase(ConcurrentMark *cm, + BitMap* region_bm, BitMap* card_bm): + _cm(cm), _region_bm(region_bm), _card_bm(card_bm) { } +}; + +// Closure that calculates the # live objects per region. Used +// for verification purposes during the cleanup pause. +class CalcLiveObjectsClosure: public CMCountDataClosureBase { + CMBitMapRO* _bm; + size_t _region_marked_bytes; + +public: + CalcLiveObjectsClosure(CMBitMapRO *bm, ConcurrentMark *cm, + BitMap* region_bm, BitMap* card_bm) : + CMCountDataClosureBase(cm, region_bm, card_bm), + _bm(bm), _region_marked_bytes(0) { } + bool doHeapRegion(HeapRegion* hr) { if (hr->continuesHumongous()) { @@ -1260,65 +1274,31 @@ size_t marked_bytes = 0; - // Below, the term "card num" means the result of shifting an address - // by the card shift -- address 0 corresponds to card number 0. One - // must subtract the card num of the bottom of the heap to obtain a - // card table index. - - // The first card num of the sequence of live cards currently being - // constructed. -1 ==> no sequence. - intptr_t start_card_num = -1; - - // The last card num of the sequence of live cards currently being - // constructed. -1 ==> no sequence. - intptr_t last_card_num = -1; - while (start < nextTop) { oop obj = oop(start); int obj_sz = obj->size(); - - // The card num of the start of the current object. - intptr_t obj_card_num = - intptr_t(uintptr_t(start) >> CardTableModRefBS::card_shift); HeapWord* obj_last = start + obj_sz - 1; - intptr_t obj_last_card_num = - intptr_t(uintptr_t(obj_last) >> CardTableModRefBS::card_shift); - - if (obj_card_num != last_card_num) { - if (start_card_num == -1) { - assert(last_card_num == -1, "Both or neither."); - start_card_num = obj_card_num; - } else { - assert(last_card_num != -1, "Both or neither."); - assert(obj_card_num >= last_card_num, "Inv"); - if ((obj_card_num - last_card_num) > 1) { - // Mark the last run, and start a new one. - mark_card_num_range(start_card_num, last_card_num); - start_card_num = obj_card_num; - } - } - } - // In any case, we set the last card num. - last_card_num = obj_last_card_num; - + + BitMap::idx_t start_idx = _cm->card_bitmap_index_for(start); + BitMap::idx_t last_idx = _cm->card_bitmap_index_for(obj_last); + + // Set the bits in the card BM for this object (inclusive). + set_card_bitmap_range(start_idx, last_idx); + + // Add the size of this object to the number of marked bytes. marked_bytes += (size_t)obj_sz * HeapWordSize; // Find the next marked object after this one. - start = _bm->getNextMarkedWordAddress(start + 1, nextTop); - } - - // Handle the last range, if any. - if (start_card_num != -1) { - mark_card_num_range(start_card_num, last_card_num); + start = _bm->getNextMarkedWordAddress(obj_last + 1, nextTop); } // Mark the allocated-since-marking portion... HeapWord* top = hr->top(); if (nextTop < top) { - start_card_num = intptr_t(uintptr_t(nextTop) >> CardTableModRefBS::card_shift); - last_card_num = intptr_t(uintptr_t(top) >> CardTableModRefBS::card_shift); - - mark_card_num_range(start_card_num, last_card_num); + BitMap::idx_t start_idx = _cm->card_bitmap_index_for(nextTop); + BitMap::idx_t last_idx = _cm->card_bitmap_index_for(top - 1); + + set_card_bitmap_range(start_idx, last_idx); // This definitely means the region has live objects. set_bit_for_region(hr); @@ -1394,17 +1374,6 @@ MutexLockerEx x((_verbose ? ParGCRareEvent_lock : NULL), Mutex::_no_safepoint_check_flag); - // Verify that _top_at_conc_count == ntams - if (hr->top_at_conc_mark_count() != hr->next_top_at_mark_start()) { - if (_verbose) { - gclog_or_tty->print_cr("Region %u: top at conc count incorrect: " - "expected " PTR_FORMAT ", actual: " PTR_FORMAT, - hr->hrs_index(), hr->next_top_at_mark_start(), - hr->top_at_conc_mark_count()); - } - failures += 1; - } - // Verify the marked bytes for this region. size_t exp_marked_bytes = _calc_cl.region_marked_bytes(); size_t act_marked_bytes = hr->next_marked_bytes(); @@ -1470,7 +1439,7 @@ _failures += failures; // We could stop iteration over the heap when we - // find the first voilating region by returning true. + // find the first violating region by returning true. return false; } }; @@ -1543,62 +1512,19 @@ int failures() const { return _failures; } }; -// Final update of count data (during cleanup). -// Adds [top_at_count, NTAMS) to the marked bytes for each -// region. Sets the bits in the card bitmap corresponding -// to the interval [top_at_count, top], and sets the -// liveness bit for each region containing live data -// in the region bitmap. - -class FinalCountDataUpdateClosure: public HeapRegionClosure { - ConcurrentMark* _cm; - BitMap* _region_bm; - BitMap* _card_bm; - - void set_card_bitmap_range(BitMap::idx_t start_idx, BitMap::idx_t last_idx) { - assert(start_idx <= last_idx, "sanity"); - - // Set the inclusive bit range [start_idx, last_idx]. - // For small ranges (up to 8 cards) use a simple loop; otherwise - // use par_at_put_range. - if ((last_idx - start_idx) <= 8) { - for (BitMap::idx_t i = start_idx; i <= last_idx; i += 1) { - _card_bm->par_set_bit(i); - } - } else { - assert(last_idx < _card_bm->size(), "sanity"); - // Note BitMap::par_at_put_range() is exclusive. - _card_bm->par_at_put_range(start_idx, last_idx+1, true); - } - } - - // It takes a region that's not empty (i.e., it has at least one - // live object in it and sets its corresponding bit on the region - // bitmap to 1. If the region is "starts humongous" it will also set - // to 1 the bits on the region bitmap that correspond to its - // associated "continues humongous" regions. - void set_bit_for_region(HeapRegion* hr) { - assert(!hr->continuesHumongous(), "should have filtered those out"); - - BitMap::idx_t index = (BitMap::idx_t) hr->hrs_index(); - if (!hr->startsHumongous()) { - // Normal (non-humongous) case: just set the bit. - _region_bm->par_set_bit(index); - } else { - // Starts humongous case: calculate how many regions are part of - // this humongous region and then set the bit range. - G1CollectedHeap* g1h = G1CollectedHeap::heap(); - HeapRegion *last_hr = g1h->heap_region_containing_raw(hr->end() - 1); - BitMap::idx_t end_index = (BitMap::idx_t) last_hr->hrs_index() + 1; - _region_bm->par_at_put_range(index, end_index, true); - } - } - +// Closure that finalizes the liveness counting data. +// Used during the cleanup pause. +// Sets the bits corresponding to the interval [NTAMS, top] +// (which contains the implicitly live objects) in the +// card liveness bitmap. Also sets the bit for each region, +// containing live data, in the region liveness bitmap. + +class FinalCountDataUpdateClosure: public CMCountDataClosureBase { public: FinalCountDataUpdateClosure(ConcurrentMark* cm, BitMap* region_bm, BitMap* card_bm) : - _cm(cm), _region_bm(region_bm), _card_bm(card_bm) { } + CMCountDataClosureBase(cm, region_bm, card_bm) { } bool doHeapRegion(HeapRegion* hr) { @@ -1613,26 +1539,10 @@ return false; } - HeapWord* start = hr->top_at_conc_mark_count(); HeapWord* ntams = hr->next_top_at_mark_start(); HeapWord* top = hr->top(); - assert(hr->bottom() <= start && start <= hr->end() && - hr->bottom() <= ntams && ntams <= hr->end(), "Preconditions."); - - if (start < ntams) { - // Region was changed between remark and cleanup pauses - // We need to add (ntams - start) to the marked bytes - // for this region, and set bits for the range - // [ card_idx(start), card_idx(ntams) ) in the card bitmap. - size_t live_bytes = (ntams - start) * HeapWordSize; - hr->add_to_marked_bytes(live_bytes); - - // Record the new top at conc count - hr->set_top_at_conc_mark_count(ntams); - - // The setting of the bits in the card bitmap takes place below - } + assert(hr->bottom() <= ntams && ntams <= hr->end(), "Preconditions."); // Mark the allocated-since-marking portion... if (ntams < top) { @@ -1640,8 +1550,8 @@ set_bit_for_region(hr); } - // Now set the bits for [start, top] - BitMap::idx_t start_idx = _cm->card_bitmap_index_for(start); + // Now set the bits for [ntams, top] + BitMap::idx_t start_idx = _cm->card_bitmap_index_for(ntams); BitMap::idx_t last_idx = _cm->card_bitmap_index_for(top); set_card_bitmap_range(start_idx, last_idx); @@ -3072,9 +2982,6 @@ // Update the marked bytes for this region. hr->add_to_marked_bytes(marked_bytes); - // Now set the top at count to NTAMS. - hr->set_top_at_conc_mark_count(limit); - // Next heap region return false; } diff -r e0d32945f6ab -r fa5227d43363 hotspot/src/share/vm/gc_implementation/g1/g1CollectedHeap.cpp --- a/hotspot/src/share/vm/gc_implementation/g1/g1CollectedHeap.cpp Thu May 10 20:05:12 2012 +0400 +++ b/hotspot/src/share/vm/gc_implementation/g1/g1CollectedHeap.cpp Thu May 10 11:47:56 2012 -0700 @@ -368,16 +368,11 @@ if (curr == NULL) gclog_or_tty->print_cr(" empty"); while (curr != NULL) { - gclog_or_tty->print_cr(" [%08x-%08x], t: %08x, P: %08x, N: %08x, C: %08x, " - "age: %4d, y: %d, surv: %d", - curr->bottom(), curr->end(), - curr->top(), + gclog_or_tty->print_cr(" "HR_FORMAT", P: "PTR_FORMAT "N: "PTR_FORMAT", age: %4d", + HR_FORMAT_PARAMS(curr), curr->prev_top_at_mark_start(), curr->next_top_at_mark_start(), - curr->top_at_conc_mark_count(), - curr->age_in_surv_rate_group_cond(), - curr->is_young(), - curr->is_survivor()); + curr->age_in_surv_rate_group_cond()); curr = curr->get_next_young_region(); } } @@ -1253,12 +1248,13 @@ IsGCActiveMark x; // Timing - bool system_gc = (gc_cause() == GCCause::_java_lang_system_gc); - assert(!system_gc || explicit_gc, "invariant"); + assert(gc_cause() != GCCause::_java_lang_system_gc || explicit_gc, "invariant"); gclog_or_tty->date_stamp(G1Log::fine() && PrintGCDateStamps); TraceCPUTime tcpu(G1Log::finer(), true, gclog_or_tty); - TraceTime t(system_gc ? "Full GC (System.gc())" : "Full GC", - G1Log::fine(), true, gclog_or_tty); + + char verbose_str[128]; + sprintf(verbose_str, "Full GC (%s)", GCCause::to_string(gc_cause())); + TraceTime t(verbose_str, G1Log::fine(), true, gclog_or_tty); TraceCollectorStats tcs(g1mm()->full_collection_counters()); TraceMemoryManagerStats tms(true /* fullGC */, gc_cause()); @@ -3593,25 +3589,22 @@ // Inner scope for scope based logging, timers, and stats collection { - char verbose_str[128]; - sprintf(verbose_str, "GC pause "); - if (g1_policy()->gcs_are_young()) { - strcat(verbose_str, "(young)"); - } else { - strcat(verbose_str, "(mixed)"); - } if (g1_policy()->during_initial_mark_pause()) { - strcat(verbose_str, " (initial-mark)"); // We are about to start a marking cycle, so we increment the // full collection counter. increment_total_full_collections(); } - // if the log level is "finer" is on, we'll print long statistics information // in the collector policy code, so let's not print this as the output // is messy if we do. gclog_or_tty->date_stamp(G1Log::fine() && PrintGCDateStamps); TraceCPUTime tcpu(G1Log::finer(), true, gclog_or_tty); + + char verbose_str[128]; + sprintf(verbose_str, "GC pause (%s) (%s)%s", + GCCause::to_string(gc_cause()), + g1_policy()->gcs_are_young() ? "young" : "mixed", + g1_policy()->during_initial_mark_pause() ? " (initial-mark)" : ""); TraceTime t(verbose_str, G1Log::fine() && !G1Log::finer(), true, gclog_or_tty); TraceCollectorStats tcs(g1mm()->incremental_collection_counters()); diff -r e0d32945f6ab -r fa5227d43363 hotspot/src/share/vm/gc_implementation/g1/g1CollectorPolicy.cpp --- a/hotspot/src/share/vm/gc_implementation/g1/g1CollectorPolicy.cpp Thu May 10 20:05:12 2012 +0400 +++ b/hotspot/src/share/vm/gc_implementation/g1/g1CollectorPolicy.cpp Thu May 10 11:47:56 2012 -0700 @@ -886,8 +886,9 @@ size_t start_used) { if (G1Log::finer()) { gclog_or_tty->stamp(PrintGCTimeStamps); - gclog_or_tty->print("[GC pause"); - gclog_or_tty->print(" (%s)", gcs_are_young() ? "young" : "mixed"); + gclog_or_tty->print("[GC pause (%s) (%s)", + GCCause::to_string(_g1->gc_cause()), + gcs_are_young() ? "young" : "mixed"); } // We only need to do this here as the policy will only be applied @@ -2459,16 +2460,10 @@ while (csr != NULL) { HeapRegion* next = csr->next_in_collection_set(); assert(csr->in_collection_set(), "bad CS"); - st->print_cr(" [%08x-%08x], t: %08x, P: %08x, N: %08x, C: %08x, " - "age: %4d, y: %d, surv: %d", - csr->bottom(), csr->end(), - csr->top(), - csr->prev_top_at_mark_start(), - csr->next_top_at_mark_start(), - csr->top_at_conc_mark_count(), - csr->age_in_surv_rate_group_cond(), - csr->is_young(), - csr->is_survivor()); + st->print_cr(" "HR_FORMAT", P: "PTR_FORMAT "N: "PTR_FORMAT", age: %4d", + HR_FORMAT_PARAMS(csr), + csr->prev_top_at_mark_start(), csr->next_top_at_mark_start(), + csr->age_in_surv_rate_group_cond()); csr = next; } } diff -r e0d32945f6ab -r fa5227d43363 hotspot/src/share/vm/gc_implementation/g1/heapRegion.cpp --- a/hotspot/src/share/vm/gc_implementation/g1/heapRegion.cpp Thu May 10 20:05:12 2012 +0400 +++ b/hotspot/src/share/vm/gc_implementation/g1/heapRegion.cpp Thu May 10 11:47:56 2012 -0700 @@ -510,9 +510,6 @@ _rem_set = new HeapRegionRemSet(sharedOffsetArray, this); assert(HeapRegionRemSet::num_par_rem_sets() > 0, "Invariant."); - // In case the region is allocated during a pause, note the top. - // We haven't done any counting on a brand new region. - _top_at_conc_mark_count = bottom(); } class NextCompactionHeapRegionClosure: public HeapRegionClosure { @@ -585,14 +582,12 @@ // we find to be self-forwarded on the next bitmap. So all // objects need to be below NTAMS. _next_top_at_mark_start = top(); - set_top_at_conc_mark_count(bottom()); _next_marked_bytes = 0; } else if (during_conc_mark) { // During concurrent mark, all objects in the CSet (including // the ones we find to be self-forwarded) are implicitly live. // So all objects need to be above NTAMS. _next_top_at_mark_start = bottom(); - set_top_at_conc_mark_count(bottom()); _next_marked_bytes = 0; } } diff -r e0d32945f6ab -r fa5227d43363 hotspot/src/share/vm/gc_implementation/g1/heapRegion.hpp --- a/hotspot/src/share/vm/gc_implementation/g1/heapRegion.hpp Thu May 10 20:05:12 2012 +0400 +++ b/hotspot/src/share/vm/gc_implementation/g1/heapRegion.hpp Thu May 10 11:47:56 2012 -0700 @@ -306,9 +306,6 @@ // If a collection pause is in progress, this is the top at the start // of that pause. - // We've counted the marked bytes of objects below here. - HeapWord* _top_at_conc_mark_count; - void init_top_at_mark_start() { assert(_prev_marked_bytes == 0 && _next_marked_bytes == 0, @@ -316,7 +313,6 @@ HeapWord* bot = bottom(); _prev_top_at_mark_start = bot; _next_top_at_mark_start = bot; - _top_at_conc_mark_count = bot; } void set_young_type(YoungType new_type) { @@ -625,19 +621,6 @@ // last mark phase ended. bool is_marked() { return _prev_top_at_mark_start != bottom(); } - void init_top_at_conc_mark_count() { - _top_at_conc_mark_count = bottom(); - } - - void set_top_at_conc_mark_count(HeapWord *cur) { - assert(bottom() <= cur && cur <= end(), "Sanity."); - _top_at_conc_mark_count = cur; - } - - HeapWord* top_at_conc_mark_count() { - return _top_at_conc_mark_count; - } - void reset_during_compaction() { guarantee( isHumongous() && startsHumongous(), "should only be called for humongous regions"); @@ -733,7 +716,6 @@ _evacuation_failed = b; if (b) { - init_top_at_conc_mark_count(); _next_marked_bytes = 0; } } diff -r e0d32945f6ab -r fa5227d43363 hotspot/src/share/vm/gc_implementation/g1/heapRegion.inline.hpp --- a/hotspot/src/share/vm/gc_implementation/g1/heapRegion.inline.hpp Thu May 10 20:05:12 2012 +0400 +++ b/hotspot/src/share/vm/gc_implementation/g1/heapRegion.inline.hpp Thu May 10 11:47:56 2012 -0700 @@ -56,7 +56,6 @@ } inline void HeapRegion::note_start_of_marking() { - init_top_at_conc_mark_count(); _next_marked_bytes = 0; _next_top_at_mark_start = top(); } diff -r e0d32945f6ab -r fa5227d43363 hotspot/src/share/vm/gc_implementation/shared/allocationStats.hpp --- a/hotspot/src/share/vm/gc_implementation/shared/allocationStats.hpp Thu May 10 20:05:12 2012 +0400 +++ b/hotspot/src/share/vm/gc_implementation/shared/allocationStats.hpp Thu May 10 11:47:56 2012 -0700 @@ -39,7 +39,7 @@ // We measure the demand between the end of the previous sweep and // beginning of this sweep: // Count(end_last_sweep) - Count(start_this_sweep) - // + splitBirths(between) - splitDeaths(between) + // + split_births(between) - split_deaths(between) // The above number divided by the time since the end of the // previous sweep gives us a time rate of demand for blocks // of this size. We compute a padded average of this rate as @@ -51,34 +51,34 @@ AdaptivePaddedAverage _demand_rate_estimate; ssize_t _desired; // Demand stimate computed as described above - ssize_t _coalDesired; // desired +/- small-percent for tuning coalescing + ssize_t _coal_desired; // desired +/- small-percent for tuning coalescing ssize_t _surplus; // count - (desired +/- small-percent), // used to tune splitting in best fit - ssize_t _bfrSurp; // surplus at start of current sweep - ssize_t _prevSweep; // count from end of previous sweep - ssize_t _beforeSweep; // count from before current sweep - ssize_t _coalBirths; // additional chunks from coalescing - ssize_t _coalDeaths; // loss from coalescing - ssize_t _splitBirths; // additional chunks from splitting - ssize_t _splitDeaths; // loss from splitting - size_t _returnedBytes; // number of bytes returned to list. + ssize_t _bfr_surp; // surplus at start of current sweep + ssize_t _prev_sweep; // count from end of previous sweep + ssize_t _before_sweep; // count from before current sweep + ssize_t _coal_births; // additional chunks from coalescing + ssize_t _coal_deaths; // loss from coalescing + ssize_t _split_births; // additional chunks from splitting + ssize_t _split_deaths; // loss from splitting + size_t _returned_bytes; // number of bytes returned to list. public: void initialize(bool split_birth = false) { AdaptivePaddedAverage* dummy = new (&_demand_rate_estimate) AdaptivePaddedAverage(CMS_FLSWeight, CMS_FLSPadding); _desired = 0; - _coalDesired = 0; + _coal_desired = 0; _surplus = 0; - _bfrSurp = 0; - _prevSweep = 0; - _beforeSweep = 0; - _coalBirths = 0; - _coalDeaths = 0; - _splitBirths = (split_birth ? 1 : 0); - _splitDeaths = 0; - _returnedBytes = 0; + _bfr_surp = 0; + _prev_sweep = 0; + _before_sweep = 0; + _coal_births = 0; + _coal_deaths = 0; + _split_births = (split_birth ? 1 : 0); + _split_deaths = 0; + _returned_bytes = 0; } AllocationStats() { @@ -99,12 +99,12 @@ // vulnerable to noisy glitches. In such cases, we // ignore the current sample and use currently available // historical estimates. - assert(prevSweep() + splitBirths() + coalBirths() // "Total Production Stock" - >= splitDeaths() + coalDeaths() + (ssize_t)count, // "Current stock + depletion" + assert(prev_sweep() + split_births() + coal_births() // "Total Production Stock" + >= split_deaths() + coal_deaths() + (ssize_t)count, // "Current stock + depletion" "Conservation Principle"); if (inter_sweep_current > _threshold) { - ssize_t demand = prevSweep() - (ssize_t)count + splitBirths() + coalBirths() - - splitDeaths() - coalDeaths(); + ssize_t demand = prev_sweep() - (ssize_t)count + split_births() + coal_births() + - split_deaths() - coal_deaths(); assert(demand >= 0, err_msg("Demand (" SSIZE_FORMAT ") should be non-negative for " PTR_FORMAT " (size=" SIZE_FORMAT ")", @@ -130,40 +130,40 @@ ssize_t desired() const { return _desired; } void set_desired(ssize_t v) { _desired = v; } - ssize_t coalDesired() const { return _coalDesired; } - void set_coalDesired(ssize_t v) { _coalDesired = v; } + ssize_t coal_desired() const { return _coal_desired; } + void set_coal_desired(ssize_t v) { _coal_desired = v; } ssize_t surplus() const { return _surplus; } void set_surplus(ssize_t v) { _surplus = v; } void increment_surplus() { _surplus++; } void decrement_surplus() { _surplus--; } - ssize_t bfrSurp() const { return _bfrSurp; } - void set_bfrSurp(ssize_t v) { _bfrSurp = v; } - ssize_t prevSweep() const { return _prevSweep; } - void set_prevSweep(ssize_t v) { _prevSweep = v; } - ssize_t beforeSweep() const { return _beforeSweep; } - void set_beforeSweep(ssize_t v) { _beforeSweep = v; } + ssize_t bfr_surp() const { return _bfr_surp; } + void set_bfr_surp(ssize_t v) { _bfr_surp = v; } + ssize_t prev_sweep() const { return _prev_sweep; } + void set_prev_sweep(ssize_t v) { _prev_sweep = v; } + ssize_t before_sweep() const { return _before_sweep; } + void set_before_sweep(ssize_t v) { _before_sweep = v; } - ssize_t coalBirths() const { return _coalBirths; } - void set_coalBirths(ssize_t v) { _coalBirths = v; } - void increment_coalBirths() { _coalBirths++; } + ssize_t coal_births() const { return _coal_births; } + void set_coal_births(ssize_t v) { _coal_births = v; } + void increment_coal_births() { _coal_births++; } - ssize_t coalDeaths() const { return _coalDeaths; } - void set_coalDeaths(ssize_t v) { _coalDeaths = v; } - void increment_coalDeaths() { _coalDeaths++; } + ssize_t coal_deaths() const { return _coal_deaths; } + void set_coal_deaths(ssize_t v) { _coal_deaths = v; } + void increment_coal_deaths() { _coal_deaths++; } - ssize_t splitBirths() const { return _splitBirths; } - void set_splitBirths(ssize_t v) { _splitBirths = v; } - void increment_splitBirths() { _splitBirths++; } + ssize_t split_births() const { return _split_births; } + void set_split_births(ssize_t v) { _split_births = v; } + void increment_split_births() { _split_births++; } - ssize_t splitDeaths() const { return _splitDeaths; } - void set_splitDeaths(ssize_t v) { _splitDeaths = v; } - void increment_splitDeaths() { _splitDeaths++; } + ssize_t split_deaths() const { return _split_deaths; } + void set_split_deaths(ssize_t v) { _split_deaths = v; } + void increment_split_deaths() { _split_deaths++; } NOT_PRODUCT( - size_t returnedBytes() const { return _returnedBytes; } - void set_returnedBytes(size_t v) { _returnedBytes = v; } + size_t returned_bytes() const { return _returned_bytes; } + void set_returned_bytes(size_t v) { _returned_bytes = v; } ) }; diff -r e0d32945f6ab -r fa5227d43363 hotspot/src/share/vm/memory/binaryTreeDictionary.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/hotspot/src/share/vm/memory/binaryTreeDictionary.cpp Thu May 10 11:47:56 2012 -0700 @@ -0,0 +1,1343 @@ +/* + * Copyright (c) 2001, 2012, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + * + */ + +#include "precompiled.hpp" +#include "gc_implementation/shared/allocationStats.hpp" +#include "memory/binaryTreeDictionary.hpp" +#include "runtime/globals.hpp" +#include "utilities/ostream.hpp" +#ifndef SERIALGC +#include "gc_implementation/shared/spaceDecorator.hpp" +#include "gc_implementation/concurrentMarkSweep/freeChunk.hpp" +#endif // SERIALGC + +//////////////////////////////////////////////////////////////////////////////// +// A binary tree based search structure for free blocks. +// This is currently used in the Concurrent Mark&Sweep implementation. +//////////////////////////////////////////////////////////////////////////////// + +template +TreeChunk* TreeChunk::as_TreeChunk(Chunk* fc) { + // Do some assertion checking here. + return (TreeChunk*) fc; +} + +template +void TreeChunk::verify_tree_chunk_list() const { + TreeChunk* nextTC = (TreeChunk*)next(); + if (prev() != NULL) { // interior list node shouldn'r have tree fields + guarantee(embedded_list()->parent() == NULL && embedded_list()->left() == NULL && + embedded_list()->right() == NULL, "should be clear"); + } + if (nextTC != NULL) { + guarantee(as_TreeChunk(nextTC->prev()) == this, "broken chain"); + guarantee(nextTC->size() == size(), "wrong size"); + nextTC->verify_tree_chunk_list(); + } +} + + +template +TreeList* TreeList::as_TreeList(TreeChunk* tc) { + // This first free chunk in the list will be the tree list. + assert(tc->size() >= BinaryTreeDictionary::min_tree_chunk_size, "Chunk is too small for a TreeChunk"); + TreeList* tl = tc->embedded_list(); + tc->set_list(tl); +#ifdef ASSERT + tl->set_protecting_lock(NULL); +#endif + tl->set_hint(0); + tl->set_size(tc->size()); + tl->link_head(tc); + tl->link_tail(tc); + tl->set_count(1); + tl->init_statistics(true /* split_birth */); + tl->set_parent(NULL); + tl->set_left(NULL); + tl->set_right(NULL); + return tl; +} + +template +TreeList* TreeList::as_TreeList(HeapWord* addr, size_t size) { + TreeChunk* tc = (TreeChunk*) addr; + assert(size >= BinaryTreeDictionary::min_tree_chunk_size, "Chunk is too small for a TreeChunk"); + // The space in the heap will have been mangled initially but + // is not remangled when a free chunk is returned to the free list + // (since it is used to maintain the chunk on the free list). + assert((ZapUnusedHeapArea && + SpaceMangler::is_mangled((HeapWord*) tc->size_addr()) && + SpaceMangler::is_mangled((HeapWord*) tc->prev_addr()) && + SpaceMangler::is_mangled((HeapWord*) tc->next_addr())) || + (tc->size() == 0 && tc->prev() == NULL && tc->next() == NULL), + "Space should be clear or mangled"); + tc->set_size(size); + tc->link_prev(NULL); + tc->link_next(NULL); + TreeList* tl = TreeList::as_TreeList(tc); + return tl; +} + +template +TreeList* TreeList::remove_chunk_replace_if_needed(TreeChunk* tc) { + + TreeList* retTL = this; + Chunk* list = head(); + assert(!list || list != list->next(), "Chunk on list twice"); + assert(tc != NULL, "Chunk being removed is NULL"); + assert(parent() == NULL || this == parent()->left() || + this == parent()->right(), "list is inconsistent"); + assert(tc->is_free(), "Header is not marked correctly"); + assert(head() == NULL || head()->prev() == NULL, "list invariant"); + assert(tail() == NULL || tail()->next() == NULL, "list invariant"); + + Chunk* prevFC = tc->prev(); + TreeChunk* nextTC = TreeChunk::as_TreeChunk(tc->next()); + assert(list != NULL, "should have at least the target chunk"); + + // Is this the first item on the list? + if (tc == list) { + // The "getChunk..." functions for a TreeList will not return the + // first chunk in the list unless it is the last chunk in the list + // because the first chunk is also acting as the tree node. + // When coalescing happens, however, the first chunk in the a tree + // list can be the start of a free range. Free ranges are removed + // from the free lists so that they are not available to be + // allocated when the sweeper yields (giving up the free list lock) + // to allow mutator activity. If this chunk is the first in the + // list and is not the last in the list, do the work to copy the + // TreeList from the first chunk to the next chunk and update all + // the TreeList pointers in the chunks in the list. + if (nextTC == NULL) { + assert(prevFC == NULL, "Not last chunk in the list"); + set_tail(NULL); + set_head(NULL); + } else { + // copy embedded list. + nextTC->set_embedded_list(tc->embedded_list()); + retTL = nextTC->embedded_list(); + // Fix the pointer to the list in each chunk in the list. + // This can be slow for a long list. Consider having + // an option that does not allow the first chunk on the + // list to be coalesced. + for (TreeChunk* curTC = nextTC; curTC != NULL; + curTC = TreeChunk::as_TreeChunk(curTC->next())) { + curTC->set_list(retTL); + } + // Fix the parent to point to the new TreeList. + if (retTL->parent() != NULL) { + if (this == retTL->parent()->left()) { + retTL->parent()->set_left(retTL); + } else { + assert(this == retTL->parent()->right(), "Parent is incorrect"); + retTL->parent()->set_right(retTL); + } + } + // Fix the children's parent pointers to point to the + // new list. + assert(right() == retTL->right(), "Should have been copied"); + if (retTL->right() != NULL) { + retTL->right()->set_parent(retTL); + } + assert(left() == retTL->left(), "Should have been copied"); + if (retTL->left() != NULL) { + retTL->left()->set_parent(retTL); + } + retTL->link_head(nextTC); + assert(nextTC->is_free(), "Should be a free chunk"); + } + } else { + if (nextTC == NULL) { + // Removing chunk at tail of list + link_tail(prevFC); + } + // Chunk is interior to the list + prevFC->link_after(nextTC); + } + + // Below this point the embeded TreeList being used for the + // tree node may have changed. Don't use "this" + // TreeList*. + // chunk should still be a free chunk (bit set in _prev) + assert(!retTL->head() || retTL->size() == retTL->head()->size(), + "Wrong sized chunk in list"); + debug_only( + tc->link_prev(NULL); + tc->link_next(NULL); + tc->set_list(NULL); + bool prev_found = false; + bool next_found = false; + for (Chunk* curFC = retTL->head(); + curFC != NULL; curFC = curFC->next()) { + assert(curFC != tc, "Chunk is still in list"); + if (curFC == prevFC) { + prev_found = true; + } + if (curFC == nextTC) { + next_found = true; + } + } + assert(prevFC == NULL || prev_found, "Chunk was lost from list"); + assert(nextTC == NULL || next_found, "Chunk was lost from list"); + assert(retTL->parent() == NULL || + retTL == retTL->parent()->left() || + retTL == retTL->parent()->right(), + "list is inconsistent"); + ) + retTL->decrement_count(); + + assert(tc->is_free(), "Should still be a free chunk"); + assert(retTL->head() == NULL || retTL->head()->prev() == NULL, + "list invariant"); + assert(retTL->tail() == NULL || retTL->tail()->next() == NULL, + "list invariant"); + return retTL; +} + +template +void TreeList::return_chunk_at_tail(TreeChunk* chunk) { + assert(chunk != NULL, "returning NULL chunk"); + assert(chunk->list() == this, "list should be set for chunk"); + assert(tail() != NULL, "The tree list is embedded in the first chunk"); + // which means that the list can never be empty. + assert(!verify_chunk_in_free_list(chunk), "Double entry"); + assert(head() == NULL || head()->prev() == NULL, "list invariant"); + assert(tail() == NULL || tail()->next() == NULL, "list invariant"); + + Chunk* fc = tail(); + fc->link_after(chunk); + link_tail(chunk); + + assert(!tail() || size() == tail()->size(), "Wrong sized chunk in list"); + FreeList::increment_count(); + debug_only(increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));) + assert(head() == NULL || head()->prev() == NULL, "list invariant"); + assert(tail() == NULL || tail()->next() == NULL, "list invariant"); +} + +// Add this chunk at the head of the list. "At the head of the list" +// is defined to be after the chunk pointer to by head(). This is +// because the TreeList is embedded in the first TreeChunk in the +// list. See the definition of TreeChunk. +template +void TreeList::return_chunk_at_head(TreeChunk* chunk) { + assert(chunk->list() == this, "list should be set for chunk"); + assert(head() != NULL, "The tree list is embedded in the first chunk"); + assert(chunk != NULL, "returning NULL chunk"); + assert(!verify_chunk_in_free_list(chunk), "Double entry"); + assert(head() == NULL || head()->prev() == NULL, "list invariant"); + assert(tail() == NULL || tail()->next() == NULL, "list invariant"); + + Chunk* fc = head()->next(); + if (fc != NULL) { + chunk->link_after(fc); + } else { + assert(tail() == NULL, "List is inconsistent"); + link_tail(chunk); + } + head()->link_after(chunk); + assert(!head() || size() == head()->size(), "Wrong sized chunk in list"); + FreeList::increment_count(); + debug_only(increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));) + assert(head() == NULL || head()->prev() == NULL, "list invariant"); + assert(tail() == NULL || tail()->next() == NULL, "list invariant"); +} + +template +TreeChunk* TreeList::head_as_TreeChunk() { + assert(head() == NULL || TreeChunk::as_TreeChunk(head())->list() == this, + "Wrong type of chunk?"); + return TreeChunk::as_TreeChunk(head()); +} + +template +TreeChunk* TreeList::first_available() { + assert(head() != NULL, "The head of the list cannot be NULL"); + Chunk* fc = head()->next(); + TreeChunk* retTC; + if (fc == NULL) { + retTC = head_as_TreeChunk(); + } else { + retTC = TreeChunk::as_TreeChunk(fc); + } + assert(retTC->list() == this, "Wrong type of chunk."); + return retTC; +} + +// Returns the block with the largest heap address amongst +// those in the list for this size; potentially slow and expensive, +// use with caution! +template +TreeChunk* TreeList::largest_address() { + assert(head() != NULL, "The head of the list cannot be NULL"); + Chunk* fc = head()->next(); + TreeChunk* retTC; + if (fc == NULL) { + retTC = head_as_TreeChunk(); + } else { + // walk down the list and return the one with the highest + // heap address among chunks of this size. + Chunk* last = fc; + while (fc->next() != NULL) { + if ((HeapWord*)last < (HeapWord*)fc) { + last = fc; + } + fc = fc->next(); + } + retTC = TreeChunk::as_TreeChunk(last); + } + assert(retTC->list() == this, "Wrong type of chunk."); + return retTC; +} + +template +BinaryTreeDictionary::BinaryTreeDictionary(bool adaptive_freelists, bool splay) : + _splay(splay), _adaptive_freelists(adaptive_freelists), + _total_size(0), _total_free_blocks(0), _root(0) {} + +template +BinaryTreeDictionary::BinaryTreeDictionary(MemRegion mr, + bool adaptive_freelists, + bool splay): + _adaptive_freelists(adaptive_freelists), _splay(splay) +{ + assert(mr.word_size() >= BinaryTreeDictionary::min_tree_chunk_size, "minimum chunk size"); + + reset(mr); + assert(root()->left() == NULL, "reset check failed"); + assert(root()->right() == NULL, "reset check failed"); + assert(root()->head()->next() == NULL, "reset check failed"); + assert(root()->head()->prev() == NULL, "reset check failed"); + assert(total_size() == root()->size(), "reset check failed"); + assert(total_free_blocks() == 1, "reset check failed"); +} + +template +void BinaryTreeDictionary::inc_total_size(size_t inc) { + _total_size = _total_size + inc; +} + +template +void BinaryTreeDictionary::dec_total_size(size_t dec) { + _total_size = _total_size - dec; +} + +template +void BinaryTreeDictionary::reset(MemRegion mr) { + assert(mr.word_size() >= BinaryTreeDictionary::min_tree_chunk_size, "minimum chunk size"); + set_root(TreeList::as_TreeList(mr.start(), mr.word_size())); + set_total_size(mr.word_size()); + set_total_free_blocks(1); +} + +template +void BinaryTreeDictionary::reset(HeapWord* addr, size_t byte_size) { + MemRegion mr(addr, heap_word_size(byte_size)); + reset(mr); +} + +template +void BinaryTreeDictionary::reset() { + set_root(NULL); + set_total_size(0); + set_total_free_blocks(0); +} + +// Get a free block of size at least size from tree, or NULL. +// If a splay step is requested, the removal algorithm (only) incorporates +// a splay step as follows: +// . the search proceeds down the tree looking for a possible +// match. At the (closest) matching location, an appropriate splay step is applied +// (zig, zig-zig or zig-zag). A chunk of the appropriate size is then returned +// if available, and if it's the last chunk, the node is deleted. A deteleted +// node is replaced in place by its tree successor. +template +TreeChunk* +BinaryTreeDictionary::get_chunk_from_tree(size_t size, enum FreeBlockDictionary::Dither dither, bool splay) +{ + TreeList *curTL, *prevTL; + TreeChunk* retTC = NULL; + assert(size >= BinaryTreeDictionary::min_tree_chunk_size, "minimum chunk size"); + if (FLSVerifyDictionary) { + verify_tree(); + } + // starting at the root, work downwards trying to find match. + // Remember the last node of size too great or too small. + for (prevTL = curTL = root(); curTL != NULL;) { + if (curTL->size() == size) { // exact match + break; + } + prevTL = curTL; + if (curTL->size() < size) { // proceed to right sub-tree + curTL = curTL->right(); + } else { // proceed to left sub-tree + assert(curTL->size() > size, "size inconsistency"); + curTL = curTL->left(); + } + } + if (curTL == NULL) { // couldn't find exact match + + if (dither == FreeBlockDictionary::exactly) return NULL; + + // try and find the next larger size by walking back up the search path + for (curTL = prevTL; curTL != NULL;) { + if (curTL->size() >= size) break; + else curTL = curTL->parent(); + } + assert(curTL == NULL || curTL->count() > 0, + "An empty list should not be in the tree"); + } + if (curTL != NULL) { + assert(curTL->size() >= size, "size inconsistency"); + if (adaptive_freelists()) { + + // A candidate chunk has been found. If it is already under + // populated, get a chunk associated with the hint for this + // chunk. + if (curTL->surplus() <= 0) { + /* Use the hint to find a size with a surplus, and reset the hint. */ + TreeList* hintTL = curTL; + while (hintTL->hint() != 0) { + assert(hintTL->hint() == 0 || hintTL->hint() > hintTL->size(), + "hint points in the wrong direction"); + hintTL = find_list(hintTL->hint()); + assert(curTL != hintTL, "Infinite loop"); + if (hintTL == NULL || + hintTL == curTL /* Should not happen but protect against it */ ) { + // No useful hint. Set the hint to NULL and go on. + curTL->set_hint(0); + break; + } + assert(hintTL->size() > size, "hint is inconsistent"); + if (hintTL->surplus() > 0) { + // The hint led to a list that has a surplus. Use it. + // Set the hint for the candidate to an overpopulated + // size. + curTL->set_hint(hintTL->size()); + // Change the candidate. + curTL = hintTL; + break; + } + // The evm code reset the hint of the candidate as + // at an interim point. Why? Seems like this leaves + // the hint pointing to a list that didn't work. + // curTL->set_hint(hintTL->size()); + } + } + } + // don't waste time splaying if chunk's singleton + if (splay && curTL->head()->next() != NULL) { + semi_splay_step(curTL); + } + retTC = curTL->first_available(); + assert((retTC != NULL) && (curTL->count() > 0), + "A list in the binary tree should not be NULL"); + assert(retTC->size() >= size, + "A chunk of the wrong size was found"); + remove_chunk_from_tree(retTC); + assert(retTC->is_free(), "Header is not marked correctly"); + } + + if (FLSVerifyDictionary) { + verify(); + } + return retTC; +} + +template +TreeList* BinaryTreeDictionary::find_list(size_t size) const { + TreeList* curTL; + for (curTL = root(); curTL != NULL;) { + if (curTL->size() == size) { // exact match + break; + } + + if (curTL->size() < size) { // proceed to right sub-tree + curTL = curTL->right(); + } else { // proceed to left sub-tree + assert(curTL->size() > size, "size inconsistency"); + curTL = curTL->left(); + } + } + return curTL; +} + + +template +bool BinaryTreeDictionary::verify_chunk_in_free_list(Chunk* tc) const { + size_t size = tc->size(); + TreeList* tl = find_list(size); + if (tl == NULL) { + return false; + } else { + return tl->verify_chunk_in_free_list(tc); + } +} + +template +Chunk* BinaryTreeDictionary::find_largest_dict() const { + TreeList *curTL = root(); + if (curTL != NULL) { + while(curTL->right() != NULL) curTL = curTL->right(); + return curTL->largest_address(); + } else { + return NULL; + } +} + +// Remove the current chunk from the tree. If it is not the last +// chunk in a list on a tree node, just unlink it. +// If it is the last chunk in the list (the next link is NULL), +// remove the node and repair the tree. +template +TreeChunk* +BinaryTreeDictionary::remove_chunk_from_tree(TreeChunk* tc) { + assert(tc != NULL, "Should not call with a NULL chunk"); + assert(tc->is_free(), "Header is not marked correctly"); + + TreeList *newTL, *parentTL; + TreeChunk* retTC; + TreeList* tl = tc->list(); + debug_only( + bool removing_only_chunk = false; + if (tl == _root) { + if ((_root->left() == NULL) && (_root->right() == NULL)) { + if (_root->count() == 1) { + assert(_root->head() == tc, "Should only be this one chunk"); + removing_only_chunk = true; + } + } + } + ) + assert(tl != NULL, "List should be set"); + assert(tl->parent() == NULL || tl == tl->parent()->left() || + tl == tl->parent()->right(), "list is inconsistent"); + + bool complicated_splice = false; + + retTC = tc; + // Removing this chunk can have the side effect of changing the node + // (TreeList*) in the tree. If the node is the root, update it. + TreeList* replacementTL = tl->remove_chunk_replace_if_needed(tc); + assert(tc->is_free(), "Chunk should still be free"); + assert(replacementTL->parent() == NULL || + replacementTL == replacementTL->parent()->left() || + replacementTL == replacementTL->parent()->right(), + "list is inconsistent"); + if (tl == root()) { + assert(replacementTL->parent() == NULL, "Incorrectly replacing root"); + set_root(replacementTL); + } + debug_only( + if (tl != replacementTL) { + assert(replacementTL->head() != NULL, + "If the tree list was replaced, it should not be a NULL list"); + TreeList* rhl = replacementTL->head_as_TreeChunk()->list(); + TreeList* rtl = TreeChunk::as_TreeChunk(replacementTL->tail())->list(); + assert(rhl == replacementTL, "Broken head"); + assert(rtl == replacementTL, "Broken tail"); + assert(replacementTL->size() == tc->size(), "Broken size"); + } + ) + + // Does the tree need to be repaired? + if (replacementTL->count() == 0) { + assert(replacementTL->head() == NULL && + replacementTL->tail() == NULL, "list count is incorrect"); + // Find the replacement node for the (soon to be empty) node being removed. + // if we have a single (or no) child, splice child in our stead + if (replacementTL->left() == NULL) { + // left is NULL so pick right. right may also be NULL. + newTL = replacementTL->right(); + debug_only(replacementTL->clear_right();) + } else if (replacementTL->right() == NULL) { + // right is NULL + newTL = replacementTL->left(); + debug_only(replacementTL->clearLeft();) + } else { // we have both children, so, by patriarchal convention, + // my replacement is least node in right sub-tree + complicated_splice = true; + newTL = remove_tree_minimum(replacementTL->right()); + assert(newTL != NULL && newTL->left() == NULL && + newTL->right() == NULL, "sub-tree minimum exists"); + } + // newTL is the replacement for the (soon to be empty) node. + // newTL may be NULL. + // should verify; we just cleanly excised our replacement + if (FLSVerifyDictionary) { + verify_tree(); + } + // first make newTL my parent's child + if ((parentTL = replacementTL->parent()) == NULL) { + // newTL should be root + assert(tl == root(), "Incorrectly replacing root"); + set_root(newTL); + if (newTL != NULL) { + newTL->clear_parent(); + } + } else if (parentTL->right() == replacementTL) { + // replacementTL is a right child + parentTL->set_right(newTL); + } else { // replacementTL is a left child + assert(parentTL->left() == replacementTL, "should be left child"); + parentTL->set_left(newTL); + } + debug_only(replacementTL->clear_parent();) + if (complicated_splice) { // we need newTL to get replacementTL's + // two children + assert(newTL != NULL && + newTL->left() == NULL && newTL->right() == NULL, + "newTL should not have encumbrances from the past"); + // we'd like to assert as below: + // assert(replacementTL->left() != NULL && replacementTL->right() != NULL, + // "else !complicated_splice"); + // ... however, the above assertion is too strong because we aren't + // guaranteed that replacementTL->right() is still NULL. + // Recall that we removed + // the right sub-tree minimum from replacementTL. + // That may well have been its right + // child! So we'll just assert half of the above: + assert(replacementTL->left() != NULL, "else !complicated_splice"); + newTL->set_left(replacementTL->left()); + newTL->set_right(replacementTL->right()); + debug_only( + replacementTL->clear_right(); + replacementTL->clearLeft(); + ) + } + assert(replacementTL->right() == NULL && + replacementTL->left() == NULL && + replacementTL->parent() == NULL, + "delete without encumbrances"); + } + + assert(total_size() >= retTC->size(), "Incorrect total size"); + dec_total_size(retTC->size()); // size book-keeping + assert(total_free_blocks() > 0, "Incorrect total count"); + set_total_free_blocks(total_free_blocks() - 1); + + assert(retTC != NULL, "null chunk?"); + assert(retTC->prev() == NULL && retTC->next() == NULL, + "should return without encumbrances"); + if (FLSVerifyDictionary) { + verify_tree(); + } + assert(!removing_only_chunk || _root == NULL, "root should be NULL"); + return TreeChunk::as_TreeChunk(retTC); +} + +// Remove the leftmost node (lm) in the tree and return it. +// If lm has a right child, link it to the left node of +// the parent of lm. +template +TreeList* BinaryTreeDictionary::remove_tree_minimum(TreeList* tl) { + assert(tl != NULL && tl->parent() != NULL, "really need a proper sub-tree"); + // locate the subtree minimum by walking down left branches + TreeList* curTL = tl; + for (; curTL->left() != NULL; curTL = curTL->left()); + // obviously curTL now has at most one child, a right child + if (curTL != root()) { // Should this test just be removed? + TreeList* parentTL = curTL->parent(); + if (parentTL->left() == curTL) { // curTL is a left child + parentTL->set_left(curTL->right()); + } else { + // If the list tl has no left child, then curTL may be + // the right child of parentTL. + assert(parentTL->right() == curTL, "should be a right child"); + parentTL->set_right(curTL->right()); + } + } else { + // The only use of this method would not pass the root of the + // tree (as indicated by the assertion above that the tree list + // has a parent) but the specification does not explicitly exclude the + // passing of the root so accomodate it. + set_root(NULL); + } + debug_only( + curTL->clear_parent(); // Test if this needs to be cleared + curTL->clear_right(); // recall, above, left child is already null + ) + // we just excised a (non-root) node, we should still verify all tree invariants + if (FLSVerifyDictionary) { + verify_tree(); + } + return curTL; +} + +// Based on a simplification of the algorithm by Sleator and Tarjan (JACM 1985). +// The simplifications are the following: +// . we splay only when we delete (not when we insert) +// . we apply a single spay step per deletion/access +// By doing such partial splaying, we reduce the amount of restructuring, +// while getting a reasonably efficient search tree (we think). +// [Measurements will be needed to (in)validate this expectation.] + +template +void BinaryTreeDictionary::semi_splay_step(TreeList* tc) { + // apply a semi-splay step at the given node: + // . if root, norting needs to be done + // . if child of root, splay once + // . else zig-zig or sig-zag depending on path from grandparent + if (root() == tc) return; + warning("*** Splaying not yet implemented; " + "tree operations may be inefficient ***"); +} + +template +void BinaryTreeDictionary::insert_chunk_in_tree(Chunk* fc) { + TreeList *curTL, *prevTL; + size_t size = fc->size(); + + assert(size >= BinaryTreeDictionary::min_tree_chunk_size, "too small to be a TreeList"); + if (FLSVerifyDictionary) { + verify_tree(); + } + + fc->clear_next(); + fc->link_prev(NULL); + + // work down from the _root, looking for insertion point + for (prevTL = curTL = root(); curTL != NULL;) { + if (curTL->size() == size) // exact match + break; + prevTL = curTL; + if (curTL->size() > size) { // follow left branch + curTL = curTL->left(); + } else { // follow right branch + assert(curTL->size() < size, "size inconsistency"); + curTL = curTL->right(); + } + } + TreeChunk* tc = TreeChunk::as_TreeChunk(fc); + // This chunk is being returned to the binary tree. Its embedded + // TreeList should be unused at this point. + tc->initialize(); + if (curTL != NULL) { // exact match + tc->set_list(curTL); + curTL->return_chunk_at_tail(tc); + } else { // need a new node in tree + tc->clear_next(); + tc->link_prev(NULL); + TreeList* newTL = TreeList::as_TreeList(tc); + assert(((TreeChunk*)tc)->list() == newTL, + "List was not initialized correctly"); + if (prevTL == NULL) { // we are the only tree node + assert(root() == NULL, "control point invariant"); + set_root(newTL); + } else { // insert under prevTL ... + if (prevTL->size() < size) { // am right child + assert(prevTL->right() == NULL, "control point invariant"); + prevTL->set_right(newTL); + } else { // am left child + assert(prevTL->size() > size && prevTL->left() == NULL, "cpt pt inv"); + prevTL->set_left(newTL); + } + } + } + assert(tc->list() != NULL, "Tree list should be set"); + + inc_total_size(size); + // Method 'total_size_in_tree' walks through the every block in the + // tree, so it can cause significant performance loss if there are + // many blocks in the tree + assert(!FLSVerifyDictionary || total_size_in_tree(root()) == total_size(), "_total_size inconsistency"); + set_total_free_blocks(total_free_blocks() + 1); + if (FLSVerifyDictionary) { + verify_tree(); + } +} + +template +size_t BinaryTreeDictionary::max_chunk_size() const { + FreeBlockDictionary::verify_par_locked(); + TreeList* tc = root(); + if (tc == NULL) return 0; + for (; tc->right() != NULL; tc = tc->right()); + return tc->size(); +} + +template +size_t BinaryTreeDictionary::total_list_length(TreeList* tl) const { + size_t res; + res = tl->count(); +#ifdef ASSERT + size_t cnt; + Chunk* tc = tl->head(); + for (cnt = 0; tc != NULL; tc = tc->next(), cnt++); + assert(res == cnt, "The count is not being maintained correctly"); +#endif + return res; +} + +template +size_t BinaryTreeDictionary::total_size_in_tree(TreeList* tl) const { + if (tl == NULL) + return 0; + return (tl->size() * total_list_length(tl)) + + total_size_in_tree(tl->left()) + + total_size_in_tree(tl->right()); +} + +template +double BinaryTreeDictionary::sum_of_squared_block_sizes(TreeList* const tl) const { + if (tl == NULL) { + return 0.0; + } + double size = (double)(tl->size()); + double curr = size * size * total_list_length(tl); + curr += sum_of_squared_block_sizes(tl->left()); + curr += sum_of_squared_block_sizes(tl->right()); + return curr; +} + +template +size_t BinaryTreeDictionary::total_free_blocks_in_tree(TreeList* tl) const { + if (tl == NULL) + return 0; + return total_list_length(tl) + + total_free_blocks_in_tree(tl->left()) + + total_free_blocks_in_tree(tl->right()); +} + +template +size_t BinaryTreeDictionary::num_free_blocks() const { + assert(total_free_blocks_in_tree(root()) == total_free_blocks(), + "_total_free_blocks inconsistency"); + return total_free_blocks(); +} + +template +size_t BinaryTreeDictionary::tree_height_helper(TreeList* tl) const { + if (tl == NULL) + return 0; + return 1 + MAX2(tree_height_helper(tl->left()), + tree_height_helper(tl->right())); +} + +template +size_t BinaryTreeDictionary::treeHeight() const { + return tree_height_helper(root()); +} + +template +size_t BinaryTreeDictionary::total_nodes_helper(TreeList* tl) const { + if (tl == NULL) { + return 0; + } + return 1 + total_nodes_helper(tl->left()) + + total_nodes_helper(tl->right()); +} + +template +size_t BinaryTreeDictionary::total_nodes_in_tree(TreeList* tl) const { + return total_nodes_helper(root()); +} + +template +void BinaryTreeDictionary::dict_census_udpate(size_t size, bool split, bool birth){ + TreeList* nd = find_list(size); + if (nd) { + if (split) { + if (birth) { + nd->increment_split_births(); + nd->increment_surplus(); + } else { + nd->increment_split_deaths(); + nd->decrement_surplus(); + } + } else { + if (birth) { + nd->increment_coal_births(); + nd->increment_surplus(); + } else { + nd->increment_coal_deaths(); + nd->decrement_surplus(); + } + } + } + // A list for this size may not be found (nd == 0) if + // This is a death where the appropriate list is now + // empty and has been removed from the list. + // This is a birth associated with a LinAB. The chunk + // for the LinAB is not in the dictionary. +} + +template +bool BinaryTreeDictionary::coal_dict_over_populated(size_t size) { + if (FLSAlwaysCoalesceLarge) return true; + + TreeList* list_of_size = find_list(size); + // None of requested size implies overpopulated. + return list_of_size == NULL || list_of_size->coal_desired() <= 0 || + list_of_size->count() > list_of_size->coal_desired(); +} + +// Closures for walking the binary tree. +// do_list() walks the free list in a node applying the closure +// to each free chunk in the list +// do_tree() walks the nodes in the binary tree applying do_list() +// to each list at each node. + +template +class TreeCensusClosure : public StackObj { + protected: + virtual void do_list(FreeList* fl) = 0; + public: + virtual void do_tree(TreeList* tl) = 0; +}; + +template +class AscendTreeCensusClosure : public TreeCensusClosure { + public: + void do_tree(TreeList* tl) { + if (tl != NULL) { + do_tree(tl->left()); + do_list(tl); + do_tree(tl->right()); + } + } +}; + +template +class DescendTreeCensusClosure : public TreeCensusClosure { + public: + void do_tree(TreeList* tl) { + if (tl != NULL) { + do_tree(tl->right()); + do_list(tl); + do_tree(tl->left()); + } + } +}; + +// For each list in the tree, calculate the desired, desired +// coalesce, count before sweep, and surplus before sweep. +template +class BeginSweepClosure : public AscendTreeCensusClosure { + double _percentage; + float _inter_sweep_current; + float _inter_sweep_estimate; + float _intra_sweep_estimate; + + public: + BeginSweepClosure(double p, float inter_sweep_current, + float inter_sweep_estimate, + float intra_sweep_estimate) : + _percentage(p), + _inter_sweep_current(inter_sweep_current), + _inter_sweep_estimate(inter_sweep_estimate), + _intra_sweep_estimate(intra_sweep_estimate) { } + + void do_list(FreeList* fl) { + double coalSurplusPercent = _percentage; + fl->compute_desired(_inter_sweep_current, _inter_sweep_estimate, _intra_sweep_estimate); + fl->set_coal_desired((ssize_t)((double)fl->desired() * coalSurplusPercent)); + fl->set_before_sweep(fl->count()); + fl->set_bfr_surp(fl->surplus()); + } +}; + +// Used to search the tree until a condition is met. +// Similar to TreeCensusClosure but searches the +// tree and returns promptly when found. + +template +class TreeSearchClosure : public StackObj { + protected: + virtual bool do_list(FreeList* fl) = 0; + public: + virtual bool do_tree(TreeList* tl) = 0; +}; + +#if 0 // Don't need this yet but here for symmetry. +template +class AscendTreeSearchClosure : public TreeSearchClosure { + public: + bool do_tree(TreeList* tl) { + if (tl != NULL) { + if (do_tree(tl->left())) return true; + if (do_list(tl)) return true; + if (do_tree(tl->right())) return true; + } + return false; + } +}; +#endif + +template +class DescendTreeSearchClosure : public TreeSearchClosure { + public: + bool do_tree(TreeList* tl) { + if (tl != NULL) { + if (do_tree(tl->right())) return true; + if (do_list(tl)) return true; + if (do_tree(tl->left())) return true; + } + return false; + } +}; + +// Searches the tree for a chunk that ends at the +// specified address. +template +class EndTreeSearchClosure : public DescendTreeSearchClosure { + HeapWord* _target; + Chunk* _found; + + public: + EndTreeSearchClosure(HeapWord* target) : _target(target), _found(NULL) {} + bool do_list(FreeList* fl) { + Chunk* item = fl->head(); + while (item != NULL) { + if (item->end() == _target) { + _found = item; + return true; + } + item = item->next(); + } + return false; + } + Chunk* found() { return _found; } +}; + +template +Chunk* BinaryTreeDictionary::find_chunk_ends_at(HeapWord* target) const { + EndTreeSearchClosure etsc(target); + bool found_target = etsc.do_tree(root()); + assert(found_target || etsc.found() == NULL, "Consistency check"); + assert(!found_target || etsc.found() != NULL, "Consistency check"); + return etsc.found(); +} + +template +void BinaryTreeDictionary::begin_sweep_dict_census(double coalSurplusPercent, + float inter_sweep_current, float inter_sweep_estimate, float intra_sweep_estimate) { + BeginSweepClosure bsc(coalSurplusPercent, inter_sweep_current, + inter_sweep_estimate, + intra_sweep_estimate); + bsc.do_tree(root()); +} + +// Closures and methods for calculating total bytes returned to the +// free lists in the tree. +#ifndef PRODUCT +template +class InitializeDictReturnedBytesClosure : public AscendTreeCensusClosure { + public: + void do_list(FreeList* fl) { + fl->set_returned_bytes(0); + } +}; + +template +void BinaryTreeDictionary::initialize_dict_returned_bytes() { + InitializeDictReturnedBytesClosure idrb; + idrb.do_tree(root()); +} + +template +class ReturnedBytesClosure : public AscendTreeCensusClosure { + size_t _dict_returned_bytes; + public: + ReturnedBytesClosure() { _dict_returned_bytes = 0; } + void do_list(FreeList* fl) { + _dict_returned_bytes += fl->returned_bytes(); + } + size_t dict_returned_bytes() { return _dict_returned_bytes; } +}; + +template +size_t BinaryTreeDictionary::sum_dict_returned_bytes() { + ReturnedBytesClosure rbc; + rbc.do_tree(root()); + + return rbc.dict_returned_bytes(); +} + +// Count the number of entries in the tree. +template +class treeCountClosure : public DescendTreeCensusClosure { + public: + uint count; + treeCountClosure(uint c) { count = c; } + void do_list(FreeList* fl) { + count++; + } +}; + +template +size_t BinaryTreeDictionary::total_count() { + treeCountClosure ctc(0); + ctc.do_tree(root()); + return ctc.count; +} +#endif // PRODUCT + +// Calculate surpluses for the lists in the tree. +template +class setTreeSurplusClosure : public AscendTreeCensusClosure { + double percentage; + public: + setTreeSurplusClosure(double v) { percentage = v; } + void do_list(FreeList* fl) { + double splitSurplusPercent = percentage; + fl->set_surplus(fl->count() - + (ssize_t)((double)fl->desired() * splitSurplusPercent)); + } +}; + +template +void BinaryTreeDictionary::set_tree_surplus(double splitSurplusPercent) { + setTreeSurplusClosure sts(splitSurplusPercent); + sts.do_tree(root()); +} + +// Set hints for the lists in the tree. +template +class setTreeHintsClosure : public DescendTreeCensusClosure { + size_t hint; + public: + setTreeHintsClosure(size_t v) { hint = v; } + void do_list(FreeList* fl) { + fl->set_hint(hint); + assert(fl->hint() == 0 || fl->hint() > fl->size(), + "Current hint is inconsistent"); + if (fl->surplus() > 0) { + hint = fl->size(); + } + } +}; + +template +void BinaryTreeDictionary::set_tree_hints(void) { + setTreeHintsClosure sth(0); + sth.do_tree(root()); +} + +// Save count before previous sweep and splits and coalesces. +template +class clearTreeCensusClosure : public AscendTreeCensusClosure { + void do_list(FreeList* fl) { + fl->set_prev_sweep(fl->count()); + fl->set_coal_births(0); + fl->set_coal_deaths(0); + fl->set_split_births(0); + fl->set_split_deaths(0); + } +}; + +template +void BinaryTreeDictionary::clear_tree_census(void) { + clearTreeCensusClosure ctc; + ctc.do_tree(root()); +} + +// Do reporting and post sweep clean up. +template +void BinaryTreeDictionary::end_sweep_dict_census(double splitSurplusPercent) { + // Does walking the tree 3 times hurt? + set_tree_surplus(splitSurplusPercent); + set_tree_hints(); + if (PrintGC && Verbose) { + report_statistics(); + } + clear_tree_census(); +} + +// Print summary statistics +template +void BinaryTreeDictionary::report_statistics() const { + FreeBlockDictionary::verify_par_locked(); + gclog_or_tty->print("Statistics for BinaryTreeDictionary:\n" + "------------------------------------\n"); + size_t total_size = total_chunk_size(debug_only(NULL)); + size_t free_blocks = num_free_blocks(); + gclog_or_tty->print("Total Free Space: %d\n", total_size); + gclog_or_tty->print("Max Chunk Size: %d\n", max_chunk_size()); + gclog_or_tty->print("Number of Blocks: %d\n", free_blocks); + if (free_blocks > 0) { + gclog_or_tty->print("Av. Block Size: %d\n", total_size/free_blocks); + } + gclog_or_tty->print("Tree Height: %d\n", treeHeight()); +} + +// Print census information - counts, births, deaths, etc. +// for each list in the tree. Also print some summary +// information. +template +class PrintTreeCensusClosure : public AscendTreeCensusClosure { + int _print_line; + size_t _total_free; + FreeList _total; + + public: + PrintTreeCensusClosure() { + _print_line = 0; + _total_free = 0; + } + FreeList* total() { return &_total; } + size_t total_free() { return _total_free; } + void do_list(FreeList* fl) { + if (++_print_line >= 40) { + FreeList::print_labels_on(gclog_or_tty, "size"); + _print_line = 0; + } + fl->print_on(gclog_or_tty); + _total_free += fl->count() * fl->size() ; + total()->set_count( total()->count() + fl->count() ); + total()->set_bfr_surp( total()->bfr_surp() + fl->bfr_surp() ); + total()->set_surplus( total()->split_deaths() + fl->surplus() ); + total()->set_desired( total()->desired() + fl->desired() ); + total()->set_prev_sweep( total()->prev_sweep() + fl->prev_sweep() ); + total()->set_before_sweep(total()->before_sweep() + fl->before_sweep()); + total()->set_coal_births( total()->coal_births() + fl->coal_births() ); + total()->set_coal_deaths( total()->coal_deaths() + fl->coal_deaths() ); + total()->set_split_births(total()->split_births() + fl->split_births()); + total()->set_split_deaths(total()->split_deaths() + fl->split_deaths()); + } +}; + +template +void BinaryTreeDictionary::print_dict_census(void) const { + + gclog_or_tty->print("\nBinaryTree\n"); + FreeList::print_labels_on(gclog_or_tty, "size"); + PrintTreeCensusClosure ptc; + ptc.do_tree(root()); + + FreeList* total = ptc.total(); + FreeList::print_labels_on(gclog_or_tty, " "); + total->print_on(gclog_or_tty, "TOTAL\t"); + gclog_or_tty->print( + "total_free(words): " SIZE_FORMAT_W(16) + " growth: %8.5f deficit: %8.5f\n", + ptc.total_free(), + (double)(total->split_births() + total->coal_births() + - total->split_deaths() - total->coal_deaths()) + /(total->prev_sweep() != 0 ? (double)total->prev_sweep() : 1.0), + (double)(total->desired() - total->count()) + /(total->desired() != 0 ? (double)total->desired() : 1.0)); +} + +template +class PrintFreeListsClosure : public AscendTreeCensusClosure { + outputStream* _st; + int _print_line; + + public: + PrintFreeListsClosure(outputStream* st) { + _st = st; + _print_line = 0; + } + void do_list(FreeList* fl) { + if (++_print_line >= 40) { + FreeList::print_labels_on(_st, "size"); + _print_line = 0; + } + fl->print_on(gclog_or_tty); + size_t sz = fl->size(); + for (Chunk* fc = fl->head(); fc != NULL; + fc = fc->next()) { + _st->print_cr("\t[" PTR_FORMAT "," PTR_FORMAT ") %s", + fc, (HeapWord*)fc + sz, + fc->cantCoalesce() ? "\t CC" : ""); + } + } +}; + +template +void BinaryTreeDictionary::print_free_lists(outputStream* st) const { + + FreeList::print_labels_on(st, "size"); + PrintFreeListsClosure pflc(st); + pflc.do_tree(root()); +} + +// Verify the following tree invariants: +// . _root has no parent +// . parent and child point to each other +// . each node's key correctly related to that of its child(ren) +template +void BinaryTreeDictionary::verify_tree() const { + guarantee(root() == NULL || total_free_blocks() == 0 || + total_size() != 0, "_total_size should't be 0?"); + guarantee(root() == NULL || root()->parent() == NULL, "_root shouldn't have parent"); + verify_tree_helper(root()); +} + +template +size_t BinaryTreeDictionary::verify_prev_free_ptrs(TreeList* tl) { + size_t ct = 0; + for (Chunk* curFC = tl->head(); curFC != NULL; curFC = curFC->next()) { + ct++; + assert(curFC->prev() == NULL || curFC->prev()->is_free(), + "Chunk should be free"); + } + return ct; +} + +// Note: this helper is recursive rather than iterative, so use with +// caution on very deep trees; and watch out for stack overflow errors; +// In general, to be used only for debugging. +template +void BinaryTreeDictionary::verify_tree_helper(TreeList* tl) const { + if (tl == NULL) + return; + guarantee(tl->size() != 0, "A list must has a size"); + guarantee(tl->left() == NULL || tl->left()->parent() == tl, + "parent<-/->left"); + guarantee(tl->right() == NULL || tl->right()->parent() == tl, + "parent<-/->right");; + guarantee(tl->left() == NULL || tl->left()->size() < tl->size(), + "parent !> left"); + guarantee(tl->right() == NULL || tl->right()->size() > tl->size(), + "parent !< left"); + guarantee(tl->head() == NULL || tl->head()->is_free(), "!Free"); + guarantee(tl->head() == NULL || tl->head_as_TreeChunk()->list() == tl, + "list inconsistency"); + guarantee(tl->count() > 0 || (tl->head() == NULL && tl->tail() == NULL), + "list count is inconsistent"); + guarantee(tl->count() > 1 || tl->head() == tl->tail(), + "list is incorrectly constructed"); + size_t count = verify_prev_free_ptrs(tl); + guarantee(count == (size_t)tl->count(), "Node count is incorrect"); + if (tl->head() != NULL) { + tl->head_as_TreeChunk()->verify_tree_chunk_list(); + } + verify_tree_helper(tl->left()); + verify_tree_helper(tl->right()); +} + +template +void BinaryTreeDictionary::verify() const { + verify_tree(); + guarantee(total_size() == total_size_in_tree(root()), "Total Size inconsistency"); +} + +#ifndef SERIALGC +// Explicitly instantiate these types for FreeChunk. +template class BinaryTreeDictionary; +template class TreeChunk; +template class TreeList; +#endif // SERIALGC diff -r e0d32945f6ab -r fa5227d43363 hotspot/src/share/vm/memory/binaryTreeDictionary.hpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/hotspot/src/share/vm/memory/binaryTreeDictionary.hpp Thu May 10 11:47:56 2012 -0700 @@ -0,0 +1,329 @@ +/* + * Copyright (c) 2001, 2012, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + * + */ + +#ifndef SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP +#define SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP + +#include "memory/freeBlockDictionary.hpp" +#include "memory/freeList.hpp" + +/* + * A binary tree based search structure for free blocks. + * This is currently used in the Concurrent Mark&Sweep implementation, but + * will be used for free block management for metadata. + */ + +// A TreeList is a FreeList which can be used to maintain a +// binary tree of free lists. + +template class TreeChunk; +template class BinaryTreeDictionary; +template class AscendTreeCensusClosure; +template class DescendTreeCensusClosure; +template class DescendTreeSearchClosure; + +template +class TreeList: public FreeList { + friend class TreeChunk; + friend class BinaryTreeDictionary; + friend class AscendTreeCensusClosure; + friend class DescendTreeCensusClosure; + friend class DescendTreeSearchClosure; + + TreeList* _parent; + TreeList* _left; + TreeList* _right; + + protected: + TreeList* parent() const { return _parent; } + TreeList* left() const { return _left; } + TreeList* right() const { return _right; } + + // Wrapper on call to base class, to get the template to compile. + Chunk* head() const { return FreeList::head(); } + Chunk* tail() const { return FreeList::tail(); } + void set_head(Chunk* head) { FreeList::set_head(head); } + void set_tail(Chunk* tail) { FreeList::set_tail(tail); } + + size_t size() const { return FreeList::size(); } + + // Accessors for links in tree. + + void set_left(TreeList* tl) { + _left = tl; + if (tl != NULL) + tl->set_parent(this); + } + void set_right(TreeList* tl) { + _right = tl; + if (tl != NULL) + tl->set_parent(this); + } + void set_parent(TreeList* tl) { _parent = tl; } + + void clearLeft() { _left = NULL; } + void clear_right() { _right = NULL; } + void clear_parent() { _parent = NULL; } + void initialize() { clearLeft(); clear_right(), clear_parent(); } + + // For constructing a TreeList from a Tree chunk or + // address and size. + static TreeList* as_TreeList(TreeChunk* tc); + static TreeList* as_TreeList(HeapWord* addr, size_t size); + + // Returns the head of the free list as a pointer to a TreeChunk. + TreeChunk* head_as_TreeChunk(); + + // Returns the first available chunk in the free list as a pointer + // to a TreeChunk. + TreeChunk* first_available(); + + // Returns the block with the largest heap address amongst + // those in the list for this size; potentially slow and expensive, + // use with caution! + TreeChunk* largest_address(); + + // remove_chunk_replace_if_needed() removes the given "tc" from the TreeList. + // If "tc" is the first chunk in the list, it is also the + // TreeList that is the node in the tree. remove_chunk_replace_if_needed() + // returns the possibly replaced TreeList* for the node in + // the tree. It also updates the parent of the original + // node to point to the new node. + TreeList* remove_chunk_replace_if_needed(TreeChunk* tc); + // See FreeList. + void return_chunk_at_head(TreeChunk* tc); + void return_chunk_at_tail(TreeChunk* tc); +}; + +// A TreeChunk is a subclass of a Chunk that additionally +// maintains a pointer to the free list on which it is currently +// linked. +// A TreeChunk is also used as a node in the binary tree. This +// allows the binary tree to be maintained without any additional +// storage (the free chunks are used). In a binary tree the first +// chunk in the free list is also the tree node. Note that the +// TreeChunk has an embedded TreeList for this purpose. Because +// the first chunk in the list is distinguished in this fashion +// (also is the node in the tree), it is the last chunk to be found +// on the free list for a node in the tree and is only removed if +// it is the last chunk on the free list. + +template +class TreeChunk : public Chunk { + friend class TreeList; + TreeList* _list; + TreeList _embedded_list; // if non-null, this chunk is on _list + protected: + TreeList* embedded_list() const { return (TreeList*) &_embedded_list; } + void set_embedded_list(TreeList* v) { _embedded_list = *v; } + public: + TreeList* list() { return _list; } + void set_list(TreeList* v) { _list = v; } + static TreeChunk* as_TreeChunk(Chunk* fc); + // Initialize fields in a TreeChunk that should be + // initialized when the TreeChunk is being added to + // a free list in the tree. + void initialize() { embedded_list()->initialize(); } + + Chunk* next() const { return Chunk::next(); } + Chunk* prev() const { return Chunk::prev(); } + size_t size() const volatile { return Chunk::size(); } + + // debugging + void verify_tree_chunk_list() const; +}; + + +template +class BinaryTreeDictionary: public FreeBlockDictionary { + friend class VMStructs; + bool _splay; + size_t _total_size; + size_t _total_free_blocks; + TreeList* _root; + bool _adaptive_freelists; + + // private accessors + bool splay() const { return _splay; } + void set_splay(bool v) { _splay = v; } + void set_total_size(size_t v) { _total_size = v; } + virtual void inc_total_size(size_t v); + virtual void dec_total_size(size_t v); + size_t total_free_blocks() const { return _total_free_blocks; } + void set_total_free_blocks(size_t v) { _total_free_blocks = v; } + TreeList* root() const { return _root; } + void set_root(TreeList* v) { _root = v; } + bool adaptive_freelists() { return _adaptive_freelists; } + + // This field is added and can be set to point to the + // the Mutex used to synchronize access to the + // dictionary so that assertion checking can be done. + // For example it is set to point to _parDictionaryAllocLock. + NOT_PRODUCT(Mutex* _lock;) + + // Remove a chunk of size "size" or larger from the tree and + // return it. If the chunk + // is the last chunk of that size, remove the node for that size + // from the tree. + TreeChunk* get_chunk_from_tree(size_t size, enum FreeBlockDictionary::Dither dither, bool splay); + // Return a list of the specified size or NULL from the tree. + // The list is not removed from the tree. + TreeList* find_list (size_t size) const; + // Remove this chunk from the tree. If the removal results + // in an empty list in the tree, remove the empty list. + TreeChunk* remove_chunk_from_tree(TreeChunk* tc); + // Remove the node in the trees starting at tl that has the + // minimum value and return it. Repair the tree as needed. + TreeList* remove_tree_minimum(TreeList* tl); + void semi_splay_step(TreeList* tl); + // Add this free chunk to the tree. + void insert_chunk_in_tree(Chunk* freeChunk); + public: + + static const size_t min_tree_chunk_size = sizeof(TreeChunk)/HeapWordSize; + + void verify_tree() const; + // verify that the given chunk is in the tree. + bool verify_chunk_in_free_list(Chunk* tc) const; + private: + void verify_tree_helper(TreeList* tl) const; + static size_t verify_prev_free_ptrs(TreeList* tl); + + // Returns the total number of chunks in the list. + size_t total_list_length(TreeList* tl) const; + // Returns the total number of words in the chunks in the tree + // starting at "tl". + size_t total_size_in_tree(TreeList* tl) const; + // Returns the sum of the square of the size of each block + // in the tree starting at "tl". + double sum_of_squared_block_sizes(TreeList