diff options
author | Arnold D. Robbins <arnold@skeeve.com> | 2022-06-24 14:12:56 +0300 |
---|---|---|
committer | Arnold D. Robbins <arnold@skeeve.com> | 2022-06-24 14:12:56 +0300 |
commit | 2ae439f369f23c6ab3d2e671ce614fff32e32a38 (patch) | |
tree | b5501d07c56cbb560f0f187c36ab4b148f2386b5 /support | |
parent | d43b469f0b189cb0ed7d5aa88d1834249cc5f415 (diff) | |
download | gawk-2ae439f369f23c6ab3d2e671ce614fff32e32a38.tar.gz |
Squashed commit of the following:
commit 61f2a5e0e48e050b8f73b127202af068b8cb574b
Author: Arnold D. Robbins <arnold@skeeve.com>
Date: Fri Jun 24 11:08:22 2022 +0300
Update awkcard.in.
commit 2b84c068b0568b4efaf93f9f6ffeaf2105295de7
Author: Arnold D. Robbins <arnold@skeeve.com>
Date: Wed Jun 22 22:02:59 2022 +0300
A few more small doc updates.
commit ce3bb88b7e71e1185c243bcc22cdcc7dbb250988
Author: Arnold D. Robbins <arnold@skeeve.com>
Date: Wed Jun 22 10:33:08 2022 +0300
Doc updates.
commit 0c101d168279d1400d3954a84a231ee70862ab61
Merge: 78fd9d6f d43b469f
Author: Arnold D. Robbins <arnold@skeeve.com>
Date: Wed Jun 22 10:19:58 2022 +0300
Merge branch 'master' into feature/pma2
commit 78fd9d6f1f45688d32e77ed7eb8cb18f9a140ec8
Author: Arnold D. Robbins <arnold@skeeve.com>
Date: Mon Jun 20 08:48:35 2022 +0300
Add --persist option.
commit a6253b1b2f3eba98a42c8b39d4af8916187d7249
Merge: bedd2e70 03f79dcb
Author: Arnold D. Robbins <arnold@skeeve.com>
Date: Mon Jun 20 08:43:28 2022 +0300
Merge branch 'master' into feature/pma2
commit bedd2e706af48057805b5221886912545c16f193
Author: Arnold D. Robbins <arnold@skeeve.com>
Date: Fri Jun 17 14:40:33 2022 +0300
Fix support/ChangeLog.
commit 8da00d7e8666808ffa50ae654b5498c4ca4b7d8c
Merge: 882a6b67 f2e71851
Author: Arnold D. Robbins <arnold@skeeve.com>
Date: Fri Jun 17 14:39:48 2022 +0300
Merge branch 'master' into feature/pma2
commit 882a6b67547204800ca865b530e3f8ef51ebd20c
Merge: 5c689dd7 ae879ed7
Author: Arnold D. Robbins <arnold@skeeve.com>
Date: Fri Jun 17 14:16:36 2022 +0300
Merge branch 'master' into feature/pma2
commit 5c689dd7da7f60228a78de3710e7d4f27c3a8eb5
Author: Arnold D. Robbins <arnold@skeeve.com>
Date: Fri Jun 17 14:10:34 2022 +0300
Doc fixes and small code fixes.
commit e3e5bc101641ceda429d8d98b1558dcc8aad5b0b
Author: Arnold D. Robbins <arnold@skeeve.com>
Date: Fri Jun 17 12:33:08 2022 +0300
Updates to pma for portability.
commit c187096f20b78631fc991898e4db62c5d6a6a441
Merge: de7bb7ee 6b97a4f7
Author: Arnold D. Robbins <arnold@skeeve.com>
Date: Wed Jun 15 18:11:00 2022 +0300
Merge branch 'master' into feature/pma2
commit de7bb7ee3e6d69c6c7985f43a0f06527f438e43d
Author: Arnold D. Robbins <arnold@skeeve.com>
Date: Wed Jun 15 14:16:07 2022 +0300
Add cygwin case to m4/pma.m4.
commit d78e8b44f8b470d894b46a0ff4cafc88ce8eed29
Author: Arnold D. Robbins <arnold@skeeve.com>
Date: Tue Jun 14 22:43:52 2022 +0300
Doc updates.
commit edc9ae773547c911d38b4a6fcb71946762df1e3d
Author: Arnold D. Robbins <arnold@skeeve.com>
Date: Tue Jun 14 22:40:58 2022 +0300
Add Mac OS support to configuration machinery.
commit 37dbf039eee81652d647aa2783f4ea4cb0266f52
Author: Arnold D. Robbins <arnold@skeeve.com>
Date: Tue Jun 14 22:01:23 2022 +0300
Add --disable-pma configure option and doc for it.
commit b0774ab145fe4828e54da22e6deb850fcceafcf4
Author: Arnold D. Robbins <arnold@skeeve.com>
Date: Tue Jun 14 15:13:38 2022 +0300
Use -no-pie only for gcc and clang.
commit fdab60d8bd6d78159571d2c4e1c4d08e0684a0ab
Author: Arnold D. Robbins <arnold@skeeve.com>
Date: Mon Jun 13 22:59:00 2022 +0300
Finish doc on persistent memory.
commit 17887261a7537f2e25f6cca63e1d67a93f3a3e36
Author: Arnold D. Robbins <arnold@skeeve.com>
Date: Mon Jun 13 13:41:19 2022 +0300
Doc and code improvements.
commit 24184e361b734aff4c7c9e96b0090cfaaf351e2d
Author: Arnold D. Robbins <arnold@skeeve.com>
Date: Fri Jun 10 14:58:26 2022 +0300
Fix for non-pma build.
commit f10f4af373c7ace425f2af9a68f5d6f4daa52bb3
Author: Arnold D. Robbins <arnold@skeeve.com>
Date: Fri Jun 10 14:54:54 2022 +0300
Get persistent stuff working!
commit 920119080d877186165506ba819a548a5ea4ae85
Author: Arnold D. Robbins <arnold@skeeve.com>
Date: Fri Jun 10 10:29:53 2022 +0300
Attempt pma symbol table integration. Works in pass through mode.
commit 36ba3cb86acd0cf8b70d78391ef0b77279b57b7c
Author: Arnold D. Robbins <arnold@skeeve.com>
Date: Thu Jun 9 22:00:21 2022 +0300
Add pma support, based on env var.
Diffstat (limited to 'support')
-rw-r--r-- | support/ChangeLog | 15 | ||||
-rw-r--r-- | support/Makefile.am | 6 | ||||
-rw-r--r-- | support/Makefile.in | 62 | ||||
-rw-r--r-- | support/agpl-3.0.txt | 661 | ||||
-rw-r--r-- | support/pma.c | 663 | ||||
-rw-r--r-- | support/pma.h | 73 |
6 files changed, 1446 insertions, 34 deletions
diff --git a/support/ChangeLog b/support/ChangeLog index 408137b1..2815c594 100644 --- a/support/ChangeLog +++ b/support/ChangeLog @@ -2,6 +2,21 @@ * dfa.c, dfa.h: Sync with GNULIB. +2022-06-17 Arnold D. Robbins <arnold@skeeve.com> + + * pma.h (PMA_H_VERSION): Add "+ gawk" to the version string. + * pma.c (pma_version): Ditto. + (PGSZ): Now a variable, assigned equal to sysconf(_SC_PAGESIZE). + Allows portability to Cygwin. + (pma_init): Remove no-longer-used `ps' variable. Remove check + of PGSZ against sysconf(_SC_PAGESIZE). + +2022-06-09 Arnold D. Robbins <arnold@skeeve.com> + + * Makefile.am (libsupport_a_SOURCES): Add pma.c if we + have USE_PERSISTENT_MALLOC defined. + * pma.h, pma.c, agpl-3.0.txt: New files. + 2022-06-03 Arnold D. Robbins <arnold@skeeve.com> * dfa.c, dfa.h: Sync with GNULIB. diff --git a/support/Makefile.am b/support/Makefile.am index f209092a..9afadbd2 100644 --- a/support/Makefile.am +++ b/support/Makefile.am @@ -34,6 +34,8 @@ EXTRA_DIST = \ ChangeLog.0 \ Makefile.am \ Makefile.in \ + pma.h \ + pma.c \ regcomp.c \ regex_internal.c \ regex_internal.h \ @@ -71,6 +73,10 @@ libsupport_a_SOURCES = \ malloc/dynarray_resize.c \ malloc/dynarray_resize_clear.c +if USE_PERSISTENT_MALLOC +libsupport_a_SOURCES += pma.c pma.h +endif + # For some make's, e.g. OpenBSD, that don't define this RM = rm -f diff --git a/support/Makefile.in b/support/Makefile.in index 476e7edf..5cbf33e7 100644 --- a/support/Makefile.in +++ b/support/Makefile.in @@ -111,6 +111,7 @@ PRE_UNINSTALL = : POST_UNINSTALL = : build_triplet = @build@ host_triplet = @host@ +@USE_PERSISTENT_MALLOC_TRUE@am__append_1 = pma.c pma.h subdir = support ACLOCAL_M4 = $(top_srcdir)/aclocal.m4 am__aclocal_m4_deps = $(top_srcdir)/m4/arch.m4 \ @@ -121,8 +122,9 @@ am__aclocal_m4_deps = $(top_srcdir)/m4/arch.m4 \ $(top_srcdir)/m4/lib-prefix.m4 $(top_srcdir)/m4/libsigsegv.m4 \ $(top_srcdir)/m4/longlong.m4 $(top_srcdir)/m4/mpfr.m4 \ $(top_srcdir)/m4/nls.m4 $(top_srcdir)/m4/noreturn.m4 \ - $(top_srcdir)/m4/po.m4 $(top_srcdir)/m4/progtest.m4 \ - $(top_srcdir)/m4/readline.m4 $(top_srcdir)/m4/socket.m4 \ + $(top_srcdir)/m4/pma.m4 $(top_srcdir)/m4/po.m4 \ + $(top_srcdir)/m4/progtest.m4 $(top_srcdir)/m4/readline.m4 \ + $(top_srcdir)/m4/socket.m4 \ $(top_srcdir)/m4/triplet-transformation.m4 \ $(top_srcdir)/m4/ulonglong.m4 $(top_srcdir)/configure.ac am__configure_deps = $(am__aclocal_m4_deps) $(CONFIGURE_DEPENDENCIES) \ @@ -140,14 +142,23 @@ am__v_AR_0 = @echo " AR " $@; am__v_AR_1 = libsupport_a_AR = $(AR) $(ARFLAGS) libsupport_a_LIBADD = +am__libsupport_a_SOURCES_DIST = attribute.h cdefs.h dfa.c dfa.h \ + dynarray.h flexmember.h getopt.c getopt.h getopt1.c \ + getopt_int.h idx.h intprops.h libc-config.h localeinfo.c \ + localeinfo.h random.c random.h regex.c regex.h verify.h \ + xalloc.h malloc/dynarray.h malloc/dynarray_at_failure.c \ + malloc/dynarray_emplace_enlarge.c malloc/dynarray_finalize.c \ + malloc/dynarray_resize.c malloc/dynarray_resize_clear.c pma.c \ + pma.h am__dirstamp = $(am__leading_dot)dirstamp +@USE_PERSISTENT_MALLOC_TRUE@am__objects_1 = pma.$(OBJEXT) am_libsupport_a_OBJECTS = dfa.$(OBJEXT) getopt.$(OBJEXT) \ getopt1.$(OBJEXT) localeinfo.$(OBJEXT) random.$(OBJEXT) \ regex.$(OBJEXT) malloc/dynarray_at_failure.$(OBJEXT) \ malloc/dynarray_emplace_enlarge.$(OBJEXT) \ malloc/dynarray_finalize.$(OBJEXT) \ malloc/dynarray_resize.$(OBJEXT) \ - malloc/dynarray_resize_clear.$(OBJEXT) + malloc/dynarray_resize_clear.$(OBJEXT) $(am__objects_1) libsupport_a_OBJECTS = $(am_libsupport_a_OBJECTS) AM_V_P = $(am__v_P_@AM_V@) am__v_P_ = $(am__v_P_@AM_DEFAULT_V@) @@ -166,7 +177,7 @@ depcomp = $(SHELL) $(top_srcdir)/build-aux/depcomp am__maybe_remake_depfiles = depfiles am__depfiles_remade = ./$(DEPDIR)/dfa.Po ./$(DEPDIR)/getopt.Po \ ./$(DEPDIR)/getopt1.Po ./$(DEPDIR)/localeinfo.Po \ - ./$(DEPDIR)/random.Po ./$(DEPDIR)/regex.Po \ + ./$(DEPDIR)/pma.Po ./$(DEPDIR)/random.Po ./$(DEPDIR)/regex.Po \ malloc/$(DEPDIR)/dynarray_at_failure.Po \ malloc/$(DEPDIR)/dynarray_emplace_enlarge.Po \ malloc/$(DEPDIR)/dynarray_finalize.Po \ @@ -186,7 +197,7 @@ am__v_CCLD_ = $(am__v_CCLD_@AM_DEFAULT_V@) am__v_CCLD_0 = @echo " CCLD " $@; am__v_CCLD_1 = SOURCES = $(libsupport_a_SOURCES) -DIST_SOURCES = $(libsupport_a_SOURCES) +DIST_SOURCES = $(am__libsupport_a_SOURCES_DIST) am__can_run_installinfo = \ case $$AM_UPDATE_INFO_DIR in \ n|no|NO) false;; \ @@ -356,6 +367,8 @@ EXTRA_DIST = \ ChangeLog.0 \ Makefile.am \ Makefile.in \ + pma.h \ + pma.c \ regcomp.c \ regex_internal.c \ regex_internal.h \ @@ -365,35 +378,13 @@ EXTRA_DIST = \ # what to make and install noinst_LIBRARIES = libsupport.a -libsupport_a_SOURCES = \ - attribute.h \ - cdefs.h \ - dfa.c \ - dfa.h \ - dynarray.h \ - flexmember.h \ - getopt.c \ - getopt.h \ - getopt1.c \ - getopt_int.h \ - idx.h \ - intprops.h \ - libc-config.h \ - localeinfo.c \ - localeinfo.h \ - random.c \ - random.h \ - regex.c \ - regex.h \ - verify.h \ - xalloc.h \ - malloc/dynarray.h \ - malloc/dynarray_at_failure.c \ - malloc/dynarray_emplace_enlarge.c \ - malloc/dynarray_finalize.c \ - malloc/dynarray_resize.c \ - malloc/dynarray_resize_clear.c - +libsupport_a_SOURCES = attribute.h cdefs.h dfa.c dfa.h dynarray.h \ + flexmember.h getopt.c getopt.h getopt1.c getopt_int.h idx.h \ + intprops.h libc-config.h localeinfo.c localeinfo.h random.c \ + random.h regex.c regex.h verify.h xalloc.h malloc/dynarray.h \ + malloc/dynarray_at_failure.c malloc/dynarray_emplace_enlarge.c \ + malloc/dynarray_finalize.c malloc/dynarray_resize.c \ + malloc/dynarray_resize_clear.c $(am__append_1) # For some make's, e.g. OpenBSD, that don't define this RM = rm -f @@ -466,6 +457,7 @@ distclean-compile: @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/getopt.Po@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/getopt1.Po@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/localeinfo.Po@am__quote@ # am--include-marker +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/pma.Po@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/random.Po@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/regex.Po@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@malloc/$(DEPDIR)/dynarray_at_failure.Po@am__quote@ # am--include-marker @@ -625,6 +617,7 @@ distclean: distclean-am -rm -f ./$(DEPDIR)/getopt.Po -rm -f ./$(DEPDIR)/getopt1.Po -rm -f ./$(DEPDIR)/localeinfo.Po + -rm -f ./$(DEPDIR)/pma.Po -rm -f ./$(DEPDIR)/random.Po -rm -f ./$(DEPDIR)/regex.Po -rm -f malloc/$(DEPDIR)/dynarray_at_failure.Po @@ -681,6 +674,7 @@ maintainer-clean: maintainer-clean-am -rm -f ./$(DEPDIR)/getopt.Po -rm -f ./$(DEPDIR)/getopt1.Po -rm -f ./$(DEPDIR)/localeinfo.Po + -rm -f ./$(DEPDIR)/pma.Po -rm -f ./$(DEPDIR)/random.Po -rm -f ./$(DEPDIR)/regex.Po -rm -f malloc/$(DEPDIR)/dynarray_at_failure.Po diff --git a/support/agpl-3.0.txt b/support/agpl-3.0.txt new file mode 100644 index 00000000..be3f7b28 --- /dev/null +++ b/support/agpl-3.0.txt @@ -0,0 +1,661 @@ + GNU AFFERO GENERAL PUBLIC LICENSE + Version 3, 19 November 2007 + + Copyright (C) 2007 Free Software Foundation, Inc. <https://fsf.org/> + Everyone is permitted to copy and distribute verbatim copies + of this license document, but changing it is not allowed. + + Preamble + + The GNU Affero General Public License is a free, copyleft license for +software and other kinds of works, specifically designed to ensure +cooperation with the community in the case of network server software. + + The licenses for most software and other practical works are designed +to take away your freedom to share and change the works. By contrast, +our General Public Licenses are intended to guarantee your freedom to +share and change all versions of a program--to make sure it remains free +software for all its users. + + When we speak of free software, we are referring to freedom, not +price. Our General Public Licenses are designed to make sure that you +have the freedom to distribute copies of free software (and charge for +them if you wish), that you receive source code or can get it if you +want it, that you can change the software or use pieces of it in new +free programs, and that you know you can do these things. + + Developers that use our General Public Licenses protect your rights +with two steps: (1) assert copyright on the software, and (2) offer +you this License which gives you legal permission to copy, distribute +and/or modify the software. + + A secondary benefit of defending all users' freedom is that +improvements made in alternate versions of the program, if they +receive widespread use, become available for other developers to +incorporate. Many developers of free software are heartened and +encouraged by the resulting cooperation. However, in the case of +software used on network servers, this result may fail to come about. +The GNU General Public License permits making a modified version and +letting the public access it on a server without ever releasing its +source code to the public. + + The GNU Affero General Public License is designed specifically to +ensure that, in such cases, the modified source code becomes available +to the community. It requires the operator of a network server to +provide the source code of the modified version running there to the +users of that server. Therefore, public use of a modified version, on +a publicly accessible server, gives the public access to the source +code of the modified version. + + An older license, called the Affero General Public License and +published by Affero, was designed to accomplish similar goals. This is +a different license, not a version of the Affero GPL, but Affero has +released a new version of the Affero GPL which permits relicensing under +this license. + + The precise terms and conditions for copying, distribution and +modification follow. + + TERMS AND CONDITIONS + + 0. Definitions. + + "This License" refers to version 3 of the GNU Affero General Public License. + + "Copyright" also means copyright-like laws that apply to other kinds of +works, such as semiconductor masks. + + "The Program" refers to any copyrightable work licensed under this +License. Each licensee is addressed as "you". "Licensees" and +"recipients" may be individuals or organizations. + + To "modify" a work means to copy from or adapt all or part of the work +in a fashion requiring copyright permission, other than the making of an +exact copy. The resulting work is called a "modified version" of the +earlier work or a work "based on" the earlier work. + + A "covered work" means either the unmodified Program or a work based +on the Program. + + To "propagate" a work means to do anything with it that, without +permission, would make you directly or secondarily liable for +infringement under applicable copyright law, except executing it on a +computer or modifying a private copy. Propagation includes copying, +distribution (with or without modification), making available to the +public, and in some countries other activities as well. + + To "convey" a work means any kind of propagation that enables other +parties to make or receive copies. Mere interaction with a user through +a computer network, with no transfer of a copy, is not conveying. + + An interactive user interface displays "Appropriate Legal Notices" +to the extent that it includes a convenient and prominently visible +feature that (1) displays an appropriate copyright notice, and (2) +tells the user that there is no warranty for the work (except to the +extent that warranties are provided), that licensees may convey the +work under this License, and how to view a copy of this License. If +the interface presents a list of user commands or options, such as a +menu, a prominent item in the list meets this criterion. + + 1. Source Code. + + The "source code" for a work means the preferred form of the work +for making modifications to it. "Object code" means any non-source +form of a work. + + A "Standard Interface" means an interface that either is an official +standard defined by a recognized standards body, or, in the case of +interfaces specified for a particular programming language, one that +is widely used among developers working in that language. + + The "System Libraries" of an executable work include anything, other +than the work as a whole, that (a) is included in the normal form of +packaging a Major Component, but which is not part of that Major +Component, and (b) serves only to enable use of the work with that +Major Component, or to implement a Standard Interface for which an +implementation is available to the public in source code form. A +"Major Component", in this context, means a major essential component +(kernel, window system, and so on) of the specific operating system +(if any) on which the executable work runs, or a compiler used to +produce the work, or an object code interpreter used to run it. + + The "Corresponding Source" for a work in object code form means all +the source code needed to generate, install, and (for an executable +work) run the object code and to modify the work, including scripts to +control those activities. However, it does not include the work's +System Libraries, or general-purpose tools or generally available free +programs which are used unmodified in performing those activities but +which are not part of the work. For example, Corresponding Source +includes interface definition files associated with source files for +the work, and the source code for shared libraries and dynamically +linked subprograms that the work is specifically designed to require, +such as by intimate data communication or control flow between those +subprograms and other parts of the work. + + The Corresponding Source need not include anything that users +can regenerate automatically from other parts of the Corresponding +Source. + + The Corresponding Source for a work in source code form is that +same work. + + 2. Basic Permissions. + + All rights granted under this License are granted for the term of +copyright on the Program, and are irrevocable provided the stated +conditions are met. This License explicitly affirms your unlimited +permission to run the unmodified Program. The output from running a +covered work is covered by this License only if the output, given its +content, constitutes a covered work. This License acknowledges your +rights of fair use or other equivalent, as provided by copyright law. + + You may make, run and propagate covered works that you do not +convey, without conditions so long as your license otherwise remains +in force. You may convey covered works to others for the sole purpose +of having them make modifications exclusively for you, or provide you +with facilities for running those works, provided that you comply with +the terms of this License in conveying all material for which you do +not control copyright. Those thus making or running the covered works +for you must do so exclusively on your behalf, under your direction +and control, on terms that prohibit them from making any copies of +your copyrighted material outside their relationship with you. + + Conveying under any other circumstances is permitted solely under +the conditions stated below. Sublicensing is not allowed; section 10 +makes it unnecessary. + + 3. Protecting Users' Legal Rights From Anti-Circumvention Law. + + No covered work shall be deemed part of an effective technological +measure under any applicable law fulfilling obligations under article +11 of the WIPO copyright treaty adopted on 20 December 1996, or +similar laws prohibiting or restricting circumvention of such +measures. + + When you convey a covered work, you waive any legal power to forbid +circumvention of technological measures to the extent such circumvention +is effected by exercising rights under this License with respect to +the covered work, and you disclaim any intention to limit operation or +modification of the work as a means of enforcing, against the work's +users, your or third parties' legal rights to forbid circumvention of +technological measures. + + 4. Conveying Verbatim Copies. + + You may convey verbatim copies of the Program's source code as you +receive it, in any medium, provided that you conspicuously and +appropriately publish on each copy an appropriate copyright notice; +keep intact all notices stating that this License and any +non-permissive terms added in accord with section 7 apply to the code; +keep intact all notices of the absence of any warranty; and give all +recipients a copy of this License along with the Program. + + You may charge any price or no price for each copy that you convey, +and you may offer support or warranty protection for a fee. + + 5. Conveying Modified Source Versions. + + You may convey a work based on the Program, or the modifications to +produce it from the Program, in the form of source code under the +terms of section 4, provided that you also meet all of these conditions: + + a) The work must carry prominent notices stating that you modified + it, and giving a relevant date. + + b) The work must carry prominent notices stating that it is + released under this License and any conditions added under section + 7. This requirement modifies the requirement in section 4 to + "keep intact all notices". + + c) You must license the entire work, as a whole, under this + License to anyone who comes into possession of a copy. This + License will therefore apply, along with any applicable section 7 + additional terms, to the whole of the work, and all its parts, + regardless of how they are packaged. This License gives no + permission to license the work in any other way, but it does not + invalidate such permission if you have separately received it. + + d) If the work has interactive user interfaces, each must display + Appropriate Legal Notices; however, if the Program has interactive + interfaces that do not display Appropriate Legal Notices, your + work need not make them do so. + + A compilation of a covered work with other separate and independent +works, which are not by their nature extensions of the covered work, +and which are not combined with it such as to form a larger program, +in or on a volume of a storage or distribution medium, is called an +"aggregate" if the compilation and its resulting copyright are not +used to limit the access or legal rights of the compilation's users +beyond what the individual works permit. Inclusion of a covered work +in an aggregate does not cause this License to apply to the other +parts of the aggregate. + + 6. Conveying Non-Source Forms. + + You may convey a covered work in object code form under the terms +of sections 4 and 5, provided that you also convey the +machine-readable Corresponding Source under the terms of this License, +in one of these ways: + + a) Convey the object code in, or embodied in, a physical product + (including a physical distribution medium), accompanied by the + Corresponding Source fixed on a durable physical medium + customarily used for software interchange. + + b) Convey the object code in, or embodied in, a physical product + (including a physical distribution medium), accompanied by a + written offer, valid for at least three years and valid for as + long as you offer spare parts or customer support for that product + model, to give anyone who possesses the object code either (1) a + copy of the Corresponding Source for all the software in the + product that is covered by this License, on a durable physical + medium customarily used for software interchange, for a price no + more than your reasonable cost of physically performing this + conveying of source, or (2) access to copy the + Corresponding Source from a network server at no charge. + + c) Convey individual copies of the object code with a copy of the + written offer to provide the Corresponding Source. This + alternative is allowed only occasionally and noncommercially, and + only if you received the object code with such an offer, in accord + with subsection 6b. + + d) Convey the object code by offering access from a designated + place (gratis or for a charge), and offer equivalent access to the + Corresponding Source in the same way through the same place at no + further charge. You need not require recipients to copy the + Corresponding Source along with the object code. If the place to + copy the object code is a network server, the Corresponding Source + may be on a different server (operated by you or a third party) + that supports equivalent copying facilities, provided you maintain + clear directions next to the object code saying where to find the + Corresponding Source. Regardless of what server hosts the + Corresponding Source, you remain obligated to ensure that it is + available for as long as needed to satisfy these requirements. + + e) Convey the object code using peer-to-peer transmission, provided + you inform other peers where the object code and Corresponding + Source of the work are being offered to the general public at no + charge under subsection 6d. + + A separable portion of the object code, whose source code is excluded +from the Corresponding Source as a System Library, need not be +included in conveying the object code work. + + A "User Product" is either (1) a "consumer product", which means any +tangible personal property which is normally used for personal, family, +or household purposes, or (2) anything designed or sold for incorporation +into a dwelling. In determining whether a product is a consumer product, +doubtful cases shall be resolved in favor of coverage. For a particular +product received by a particular user, "normally used" refers to a +typical or common use of that class of product, regardless of the status +of the particular user or of the way in which the particular user +actually uses, or expects or is expected to use, the product. A product +is a consumer product regardless of whether the product has substantial +commercial, industrial or non-consumer uses, unless such uses represent +the only significant mode of use of the product. + + "Installation Information" for a User Product means any methods, +procedures, authorization keys, or other information required to install +and execute modified versions of a covered work in that User Product from +a modified version of its Corresponding Source. The information must +suffice to ensure that the continued functioning of the modified object +code is in no case prevented or interfered with solely because +modification has been made. + + If you convey an object code work under this section in, or with, or +specifically for use in, a User Product, and the conveying occurs as +part of a transaction in which the right of possession and use of the +User Product is transferred to the recipient in perpetuity or for a +fixed term (regardless of how the transaction is characterized), the +Corresponding Source conveyed under this section must be accompanied +by the Installation Information. But this requirement does not apply +if neither you nor any third party retains the ability to install +modified object code on the User Product (for example, the work has +been installed in ROM). + + The requirement to provide Installation Information does not include a +requirement to continue to provide support service, warranty, or updates +for a work that has been modified or installed by the recipient, or for +the User Product in which it has been modified or installed. Access to a +network may be denied when the modification itself materially and +adversely affects the operation of the network or violates the rules and +protocols for communication across the network. + + Corresponding Source conveyed, and Installation Information provided, +in accord with this section must be in a format that is publicly +documented (and with an implementation available to the public in +source code form), and must require no special password or key for +unpacking, reading or copying. + + 7. Additional Terms. + + "Additional permissions" are terms that supplement the terms of this +License by making exceptions from one or more of its conditions. +Additional permissions that are applicable to the entire Program shall +be treated as though they were included in this License, to the extent +that they are valid under applicable law. If additional permissions +apply only to part of the Program, that part may be used separately +under those permissions, but the entire Program remains governed by +this License without regard to the additional permissions. + + When you convey a copy of a covered work, you may at your option +remove any additional permissions from that copy, or from any part of +it. (Additional permissions may be written to require their own +removal in certain cases when you modify the work.) You may place +additional permissions on material, added by you to a covered work, +for which you have or can give appropriate copyright permission. + + Notwithstanding any other provision of this License, for material you +add to a covered work, you may (if authorized by the copyright holders of +that material) supplement the terms of this License with terms: + + a) Disclaiming warranty or limiting liability differently from the + terms of sections 15 and 16 of this License; or + + b) Requiring preservation of specified reasonable legal notices or + author attributions in that material or in the Appropriate Legal + Notices displayed by works containing it; or + + c) Prohibiting misrepresentation of the origin of that material, or + requiring that modified versions of such material be marked in + reasonable ways as different from the original version; or + + d) Limiting the use for publicity purposes of names of licensors or + authors of the material; or + + e) Declining to grant rights under trademark law for use of some + trade names, trademarks, or service marks; or + + f) Requiring indemnification of licensors and authors of that + material by anyone who conveys the material (or modified versions of + it) with contractual assumptions of liability to the recipient, for + any liability that these contractual assumptions directly impose on + those licensors and authors. + + All other non-permissive additional terms are considered "further +restrictions" within the meaning of section 10. If the Program as you +received it, or any part of it, contains a notice stating that it is +governed by this License along with a term that is a further +restriction, you may remove that term. If a license document contains +a further restriction but permits relicensing or conveying under this +License, you may add to a covered work material governed by the terms +of that license document, provided that the further restriction does +not survive such relicensing or conveying. + + If you add terms to a covered work in accord with this section, you +must place, in the relevant source files, a statement of the +additional terms that apply to those files, or a notice indicating +where to find the applicable terms. + + Additional terms, permissive or non-permissive, may be stated in the +form of a separately written license, or stated as exceptions; +the above requirements apply either way. + + 8. Termination. + + You may not propagate or modify a covered work except as expressly +provided under this License. Any attempt otherwise to propagate or +modify it is void, and will automatically terminate your rights under +this License (including any patent licenses granted under the third +paragraph of section 11). + + However, if you cease all violation of this License, then your +license from a particular copyright holder is reinstated (a) +provisionally, unless and until the copyright holder explicitly and +finally terminates your license, and (b) permanently, if the copyright +holder fails to notify you of the violation by some reasonable means +prior to 60 days after the cessation. + + Moreover, your license from a particular copyright holder is +reinstated permanently if the copyright holder notifies you of the +violation by some reasonable means, this is the first time you have +received notice of violation of this License (for any work) from that +copyright holder, and you cure the violation prior to 30 days after +your receipt of the notice. + + Termination of your rights under this section does not terminate the +licenses of parties who have received copies or rights from you under +this License. If your rights have been terminated and not permanently +reinstated, you do not qualify to receive new licenses for the same +material under section 10. + + 9. Acceptance Not Required for Having Copies. + + You are not required to accept this License in order to receive or +run a copy of the Program. Ancillary propagation of a covered work +occurring solely as a consequence of using peer-to-peer transmission +to receive a copy likewise does not require acceptance. However, +nothing other than this License grants you permission to propagate or +modify any covered work. These actions infringe copyright if you do +not accept this License. Therefore, by modifying or propagating a +covered work, you indicate your acceptance of this License to do so. + + 10. Automatic Licensing of Downstream Recipients. + + Each time you convey a covered work, the recipient automatically +receives a license from the original licensors, to run, modify and +propagate that work, subject to this License. You are not responsible +for enforcing compliance by third parties with this License. + + An "entity transaction" is a transaction transferring control of an +organization, or substantially all assets of one, or subdividing an +organization, or merging organizations. If propagation of a covered +work results from an entity transaction, each party to that +transaction who receives a copy of the work also receives whatever +licenses to the work the party's predecessor in interest had or could +give under the previous paragraph, plus a right to possession of the +Corresponding Source of the work from the predecessor in interest, if +the predecessor has it or can get it with reasonable efforts. + + You may not impose any further restrictions on the exercise of the +rights granted or affirmed under this License. For example, you may +not impose a license fee, royalty, or other charge for exercise of +rights granted under this License, and you may not initiate litigation +(including a cross-claim or counterclaim in a lawsuit) alleging that +any patent claim is infringed by making, using, selling, offering for +sale, or importing the Program or any portion of it. + + 11. Patents. + + A "contributor" is a copyright holder who authorizes use under this +License of the Program or a work on which the Program is based. The +work thus licensed is called the contributor's "contributor version". + + A contributor's "essential patent claims" are all patent claims +owned or controlled by the contributor, whether already acquired or +hereafter acquired, that would be infringed by some manner, permitted +by this License, of making, using, or selling its contributor version, +but do not include claims that would be infringed only as a +consequence of further modification of the contributor version. For +purposes of this definition, "control" includes the right to grant +patent sublicenses in a manner consistent with the requirements of +this License. + + Each contributor grants you a non-exclusive, worldwide, royalty-free +patent license under the contributor's essential patent claims, to +make, use, sell, offer for sale, import and otherwise run, modify and +propagate the contents of its contributor version. + + In the following three paragraphs, a "patent license" is any express +agreement or commitment, however denominated, not to enforce a patent +(such as an express permission to practice a patent or covenant not to +sue for patent infringement). To "grant" such a patent license to a +party means to make such an agreement or commitment not to enforce a +patent against the party. + + If you convey a covered work, knowingly relying on a patent license, +and the Corresponding Source of the work is not available for anyone +to copy, free of charge and under the terms of this License, through a +publicly available network server or other readily accessible means, +then you must either (1) cause the Corresponding Source to be so +available, or (2) arrange to deprive yourself of the benefit of the +patent license for this particular work, or (3) arrange, in a manner +consistent with the requirements of this License, to extend the patent +license to downstream recipients. "Knowingly relying" means you have +actual knowledge that, but for the patent license, your conveying the +covered work in a country, or your recipient's use of the covered work +in a country, would infringe one or more identifiable patents in that +country that you have reason to believe are valid. + + If, pursuant to or in connection with a single transaction or +arrangement, you convey, or propagate by procuring conveyance of, a +covered work, and grant a patent license to some of the parties +receiving the covered work authorizing them to use, propagate, modify +or convey a specific copy of the covered work, then the patent license +you grant is automatically extended to all recipients of the covered +work and works based on it. + + A patent license is "discriminatory" if it does not include within +the scope of its coverage, prohibits the exercise of, or is +conditioned on the non-exercise of one or more of the rights that are +specifically granted under this License. You may not convey a covered +work if you are a party to an arrangement with a third party that is +in the business of distributing software, under which you make payment +to the third party based on the extent of your activity of conveying +the work, and under which the third party grants, to any of the +parties who would receive the covered work from you, a discriminatory +patent license (a) in connection with copies of the covered work +conveyed by you (or copies made from those copies), or (b) primarily +for and in connection with specific products or compilations that +contain the covered work, unless you entered into that arrangement, +or that patent license was granted, prior to 28 March 2007. + + Nothing in this License shall be construed as excluding or limiting +any implied license or other defenses to infringement that may +otherwise be available to you under applicable patent law. + + 12. No Surrender of Others' Freedom. + + If conditions are imposed on you (whether by court order, agreement or +otherwise) that contradict the conditions of this License, they do not +excuse you from the conditions of this License. If you cannot convey a +covered work so as to satisfy simultaneously your obligations under this +License and any other pertinent obligations, then as a consequence you may +not convey it at all. For example, if you agree to terms that obligate you +to collect a royalty for further conveying from those to whom you convey +the Program, the only way you could satisfy both those terms and this +License would be to refrain entirely from conveying the Program. + + 13. Remote Network Interaction; Use with the GNU General Public License. + + Notwithstanding any other provision of this License, if you modify the +Program, your modified version must prominently offer all users +interacting with it remotely through a computer network (if your version +supports such interaction) an opportunity to receive the Corresponding +Source of your version by providing access to the Corresponding Source +from a network server at no charge, through some standard or customary +means of facilitating copying of software. This Corresponding Source +shall include the Corresponding Source for any work covered by version 3 +of the GNU General Public License that is incorporated pursuant to the +following paragraph. + + Notwithstanding any other provision of this License, you have +permission to link or combine any covered work with a work licensed +under version 3 of the GNU General Public License into a single +combined work, and to convey the resulting work. The terms of this +License will continue to apply to the part which is the covered work, +but the work with which it is combined will remain governed by version +3 of the GNU General Public License. + + 14. Revised Versions of this License. + + The Free Software Foundation may publish revised and/or new versions of +the GNU Affero General Public License from time to time. Such new versions +will be similar in spirit to the present version, but may differ in detail to +address new problems or concerns. + + Each version is given a distinguishing version number. If the +Program specifies that a certain numbered version of the GNU Affero General +Public License "or any later version" applies to it, you have the +option of following the terms and conditions either of that numbered +version or of any later version published by the Free Software +Foundation. If the Program does not specify a version number of the +GNU Affero General Public License, you may choose any version ever published +by the Free Software Foundation. + + If the Program specifies that a proxy can decide which future +versions of the GNU Affero General Public License can be used, that proxy's +public statement of acceptance of a version permanently authorizes you +to choose that version for the Program. + + Later license versions may give you additional or different +permissions. However, no additional obligations are imposed on any +author or copyright holder as a result of your choosing to follow a +later version. + + 15. Disclaimer of Warranty. + + THERE IS NO WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY +APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT +HOLDERS AND/OR OTHER PARTIES PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY +OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, +THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR +PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM +IS WITH YOU. SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF +ALL NECESSARY SERVICING, REPAIR OR CORRECTION. + + 16. Limitation of Liability. + + IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING +WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MODIFIES AND/OR CONVEYS +THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, INCLUDING ANY +GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE +USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED TO LOSS OF +DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD +PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS), +EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF +SUCH DAMAGES. + + 17. Interpretation of Sections 15 and 16. + + If the disclaimer of warranty and limitation of liability provided +above cannot be given local legal effect according to their terms, +reviewing courts shall apply local law that most closely approximates +an absolute waiver of all civil liability in connection with the +Program, unless a warranty or assumption of liability accompanies a +copy of the Program in return for a fee. + + END OF TERMS AND CONDITIONS + + How to Apply These Terms to Your New Programs + + If you develop a new program, and you want it to be of the greatest +possible use to the public, the best way to achieve this is to make it +free software which everyone can redistribute and change under these terms. + + To do so, attach the following notices to the program. It is safest +to attach them to the start of each source file to most effectively +state the exclusion of warranty; and each file should have at least +the "copyright" line and a pointer to where the full notice is found. + + <one line to give the program's name and a brief idea of what it does.> + Copyright (C) <year> <name of author> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program 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 Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. + +Also add information on how to contact you by electronic and paper mail. + + If your software can interact with users remotely through a computer +network, you should also make sure that it provides a way for users to +get its source. For example, if your program is a web application, its +interface could display a "Source" link that leads users to an archive +of the code. There are many ways you could offer source, and different +solutions will be better for different programs; see section 13 for the +specific requirements. + + You should also get your employer (if you work as a programmer) or school, +if any, to sign a "copyright disclaimer" for the program, if necessary. +For more information on this, and how to apply and follow the GNU AGPL, see +<https://www.gnu.org/licenses/>. diff --git a/support/pma.c b/support/pma.c new file mode 100644 index 00000000..da4d0b9a --- /dev/null +++ b/support/pma.c @@ -0,0 +1,663 @@ +/* "pma", a persistent memory allocator (implementation) + Copyright (C) 2019, 2022 Terence Kelly + Contact: tpkelly @ { acm.org, cs.princeton.edu, eecs.umich.edu } + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program 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 Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. + + Code is intended to be (mostly) C99 / POSIX 2017. + + Compile and link with your programs in the obvious way. If + assertions are enabled (the default) extensive integrity checks + are frequently performed; these checks may be slow, depending on + the size and state of the persistent heap. +*/ + +#define _DEFAULT_SOURCE // for MAP_ANONYMOUS +#include <assert.h> +#include <errno.h> +#include <fcntl.h> +#include <inttypes.h> +#include <limits.h> +#include <math.h> +#include <stdio.h> +#include <string.h> +#include <stdlib.h> +#include <unistd.h> +#include <sys/mman.h> +#include <sys/stat.h> +#include <sys/types.h> + +#include "pma.h" + +// Software version; not the same as backing file format version. +const char pma_version[] = "2022.05May.01 (Avon 5) + gawk"; + +#define S(s) #s +#define S2(s) S(s) +#define COORDS __FILE__ ":" S2(__LINE__) ": " +#define FP(...) (void)fprintf(stderr, COORDS __VA_ARGS__) +#define ERN " errno => '%s'\n", strerror(errno) +#define ERR(...) do { if (0 < state.vrb) FP("ERROR: " __VA_ARGS__); } while (0) +#define WRN(...) do { if (1 < state.vrb) FP("Warning: " __VA_ARGS__); } while (0) +#define FYI(...) do { if (2 < state.vrb) FP("FYI: " __VA_ARGS__); } while (0) + +int pma_errno; +#define SE pma_errno = __LINE__ +#define RL return __LINE__ +#define RN return NULL +#define SERL do { SE; RL; } while (0) +#define SERN do { SE; RN; } while (0) + +enum { + VERS = 2, // backing file format version number + WDSZ = 8, // word size (bytes) + NFL = 422 // number of free lists / size classes +}; + +static int PGSZ; // can vary per system and even dynamically + +typedef struct ao { // alloc object + struct ao *anext, // header; singly linked list of all aos in addr order + *fprev, *fnext; // for doubly linked free list +} ao_t; + +// We stash three flags in the least significant bits of a header: +// bit 0: is this ao in use (i.e., live, as opposed to free)? +// bit 1: is the previous ao on the state.anext list in use? +// bit 2: has this ao ever grown via realloc? + +// Some older compilers gratuitously reject the himask definition on +// the first line below despite it being perfectly legal C99. The +// workaround on the second line below appears correct by inspection +// but it has not yet been subjected to the same extensive tests as +// the original. +// static const uintptr_t lomask = 0x7, himask = ~lomask; // requires recent compiler +static const uintptr_t lomask = 0x7, himask = ~ ( (uintptr_t) 0x7 ); // not extensively tested as of Fri 27 May 2022 + +// extract bits from header +#define HIBH(ao_t_ptr) ((ao_t *)((uintptr_t)(ao_t_ptr) & himask)) +#define LOBH(ao_t_ptr) ((ao_t *)((uintptr_t)(ao_t_ptr) & lomask)) + +// size of an ao is its memory footprint; capacity of ao is number of bytes +// available to caller; difference is header overhead of live (in-use) ao +#define AOSZ(ao_t_ptr) ((size_t)((uintptr_t)HIBH((ao_t_ptr)->anext) - (uintptr_t)HIBH(ao_t_ptr))) +#define AOCAP(ao_t_ptr) (AOSZ(ao_t_ptr) - WDSZ) + +#define Z1(i) assert(0 == (i) || 1 == (i)) +static void slobh(ao_t *p, int iu, int piu, int grown) { // set low bits of header to which p points + uintptr_t h; + assert(p); Z1(iu); Z1(piu); Z1(grown); + h = (uintptr_t)p->anext; + h &= himask; // clear low bits + h |= (uintptr_t)(iu | piu << 1 | grown << 2); + p->anext = (ao_t *)h; +} + +// getters below could be re-written as simpler macros + +static void globh(const ao_t *p, int *iu, int *piu, int *grown) { // get low bits of header to which p points + uintptr_t h; + assert(p && iu && piu && grown); + h = (uintptr_t)p->anext; + *iu = !!(h & 0x1); Z1(*iu); + *piu = !!(h & 0x2); Z1(*piu); + *grown = !!(h & 0x4); Z1(*grown); +} + +typedef struct { // header of backing file; contains allocator metadata + void * mapaddr; // virtual address where backing file must be mapped + uint64_t bf_vers, // version number of backing file format + nallocs, // number of allocations + nfrees, // number of de-allocations + res_0; // reserved for possible future use + void * root; // live persistent data must be reachable from root + ao_t * afirst, // list of all alloc objects, both live & free, in addr order + * abound; // one beyond end of allocatable area + ao_t free[NFL]; // free lists; each has dummy header +} pma_hdr_t; + +static struct { + int init, // has persistent heap been initialized? + vrb; // verbsity level + const char * file; // name of backing file + pma_hdr_t * hdr; // addr where backing file is mapped +} state; + +#define ASI assert(1 == state.init || 2 == state.init) + +enum { IU = 0, PIU = 1, GROWN = 2 }; + +static int getbit(ao_t *p, int bit) { + int iu, piu, grown; + globh(p, &iu, &piu, &grown); + switch (bit) { + case IU: return iu; + case PIU: return piu; + case GROWN: return grown; + default: + ERR("bad bit: %d\n", bit); + assert(0); + return INT_MIN; + } +} + +#define DP(...) (void)fprintf(stderr, __VA_ARGS__) +#define VS (void *) + +#ifndef NDEBUG +static int valid_footer(ao_t *p) { + if (!getbit(p, IU)) { + ao_t **ftr = (ao_t **)HIBH(p->anext) - 1; + return *ftr == p; // footer should point to header + } + else + return 1; +} +// valid ao ptr: +#define VAO(p) (VS state.hdr->afirst <= VS (p) && VS state.hdr->abound > VS (p)) +#define VAF(p) (VAO(p) && valid_footer(p)) +#endif // NDEBUG + +static void pao(ao_t *p) { // print ao + int iu, piu, grown; + ao_t **footer = (ao_t **) ((char *)p + AOSZ(p)) - 1; // TODO: squelch alignment warning? + assert(VAO(p)); + assert(0 == AOSZ(p) % WDSZ); + assert(0 == LOBH(p)); + globh(p, &iu, &piu, &grown); + DP(" AO at %p: size %lu B / %lu w\n" + " hdr %p (H 0%lo L 0%lo) iu %d piu %d grown %d\n" + " fp %p%s\n" + " fn %p%s\n" + " ft %p%s\n", + VS p, AOSZ(p), AOSZ(p) / WDSZ, + VS p->anext, (uintptr_t)HIBH(p->anext), (uintptr_t)LOBH(p->anext), iu, piu, grown, + VS p->fprev, iu ? " (ignore)" : "", + VS p->fnext, iu ? " (ignore)" : "", + VS *footer, iu ? " (ignore)" : ""); +} + +static size_t UB[NFL]; // UB[c] is upper bound of size class c in machine words + +#define IC integrity_check(__LINE__) +static int integrity_check(int line) { // can be slow; intended for debugging small heaps + pma_hdr_t *h = state.hdr; + int nadd = 0, naddfree = 0, tiu = 0, tpiu = 0, tf = 0; // beware overflow if lists are long + FYI("integrity_check called from line %d\n", line); +#ifdef NDEBUG + WRN("integrity check relies on assertions, which are disabled (call at line %d)\n", line); +#endif + assert(h && h == h->mapaddr); + // check addr-ordered list + for (ao_t *next, *a = h->afirst; a < h->abound; a = next) { + next = HIBH(a->anext); + assert(VAF(a)); + assert(32 <= AOSZ(a)); + assert(next > a && next <= h->abound); + if (1000000 < ++nadd) { + WRN("integrity check discontinued; anext list too long (call at line %d)\n", line); + SE; // if persistent heap contains too many aos/blocks, + return 0; // integrity check will be too slow; therefore discontinue + } + if (0 == getbit(a, IU)) + ++naddfree; + tiu += getbit(a, IU); // total number of aos with in-use bit set + tpiu += getbit(a, PIU); // total number of aos with previous-ao-is-in-use bit set + } + assert(tpiu == tiu || 1 + tpiu == tiu); + FYI("anext list length: %d tiu %d tpiu %d nallocs %lu nfrees %lu\n", + nadd, tiu, tpiu, h->nallocs, h->nfrees); + assert(h->nallocs >= h->nfrees); + assert(h->nallocs - h->nfrees == (uint64_t)tiu); + // check free lists + for (int i = 0; i < NFL; i++) { + ao_t *p, *f = &(h->free[i]); + if (f->fprev == f) // empty list + assert(f->fnext == f); + else { + int nfwd = 0, nrev = 0; // count how many we find going forward and reverse + for (p = f->fnext; p != f; p = p->fnext) { nfwd++; assert(VAF(p)); assert(0 == getbit(p, IU)); } + for (p = f->fprev; p != f; p = p->fprev) { nrev++; assert(VAF(p)); assert(0 == getbit(p, IU)); } + assert(nfwd == nrev); // count should be the same in both directions + tf += nfwd; + // check ao sizes against UB + for (p = f->fnext; p != f; p = p->fnext) { + #ifndef NDEBUG + size_t capwords = AOCAP(p) / WDSZ; + #endif + assert(capwords <= UB[i]); + if (0 < i) + assert(capwords > UB[i-1]); + } + } + } + FYI("total free aos: %d naddfree %d integrity check line %d\n", tf, naddfree, line); + assert(tf == naddfree); + return 0; +} + +#define NM " not meaningful in fallback mode\n" + +void pma_check_and_dump(void) { + pma_hdr_t *h = state.hdr; + ASI; + if (2 == state.init) { ERR("check_and_dump" NM); assert(0); SE; return; } + if (IC) ERR("integrity check failed\n"); + DP(COORDS "check data structures and dump\n"); + DP("header version: %s\n", PMA_H_VERSION); + DP("software version: %s\n", pma_version); + DP("sizeof state: %lu\n", sizeof state); + DP("sizeof header: %lu\n", sizeof(pma_hdr_t)); + DP("state:\n"); + DP(" init: %d\n", state.init); assert(0 == state.init || 1 == state.init || 2 == state.init); + DP(" vrb: %d\n", state.vrb); assert(0 <= state.vrb && 3 >= state.vrb); + DP(" file: %p \"%s\"\n", (const void *)state.file, state.file); + DP(" hdr: %p\n", VS h); + if (NULL != h) { + DP("header:\n"); // nallocs & nfrees not printed; they'd add noise to initial/final state diff + DP(" mapaddr: %p\n", h->mapaddr); + DP(" bf_vers: %" PRIu64 "\n", h->bf_vers); + DP(" root: %p\n", h->root); assert(NULL == h->root || (h->root >= VS h->afirst && h->root < VS h->abound)); + DP(" afirst: %p\n", VS h->afirst); assert(VS h->afirst > h->mapaddr); + DP(" abound: %p\n", VS h->abound); assert(h->abound > h->afirst); + DP(" all allocated objects in addr order:\n"); + for (ao_t *a = h->afirst; a < h->abound; a = HIBH(a->anext)) { + assert(HIBH(a->anext) > a); + pao(a); + } + for (int i = 0; i < NFL; i++) { + ao_t *f = &(h->free[i]); + if (f->fprev == f) // empty list + assert(f->fnext == f); + else { + DP(" free list of size class %d UB %lu (prev %lu) list head %p:\n", i, UB[i], i > 0 ? UB[i-1] : 0, VS f); + for (ao_t *p = f->fnext; p != f; p = p->fnext) + pao(p); + } + } + } +} +#undef DP + +static int sc(size_t nbytes) { // compute size class; nbytes is malloc() arg + static int init; + const size_t maxwords = (size_t)0x1 << 61; // 2^61 words == 2^64 bytes + size_t nwords; + int c; + if (! init) { + FYI("initializing UB[]\n"); + UB[0] = 3; // smallest allocation has size (AOSZ) 4 words and capacity (AOCAP) 3 words + for (c = 1; ; c++) { + long double hi = floorl((long double)(1 + UB[c-1]) * 1.1L); + assert(NFL > c); + if (hi >= (long double)maxwords) { UB[c] = maxwords; break; } + else UB[c] = (size_t)hi; + } + assert(NFL - 1 == c); + init = 1; + } + nwords = (nbytes / WDSZ) + !!(nbytes % WDSZ); + assert(nwords <= maxwords); + for (c = 0; NFL > c; c++) + if (nwords <= UB[c]) + break; + assert(NFL > c); + return c; +} + +static void fli(ao_t *p) { // insert given ao at head of appropriate free list + ao_t *h; + int fl; + assert(NULL != p); + assert(VAO(p)); + fl = sc(AOCAP(p)); + assert(0 <= fl && NFL > fl); + h = &(state.hdr->free[fl]); // head of free list + FYI("fli(%p) h == %p h->fn %p h->fp %p\n", VS p, VS h, VS h->fnext, VS h->fprev); + p->fprev = h; + p->fnext = h->fnext; + h->fnext->fprev = p; + h->fnext = p; +} + +static void flr(ao_t *p) { // remove ao from free list + p->fnext->fprev = p->fprev; + p->fprev->fnext = p->fnext; + p->fprev = p->fnext = NULL; +} + +#define MMAP(N) mmap(NULL, (N), PROT_NONE, MAP_PRIVATE | MAP_ANONYMOUS | MAP_NORESERVE, -1, 0) +#define MUNMAP(A, N) do { if (0 != munmap((A), (N))) ERR("mmap()" ERN); } while (0) +static void * addrgap(off_t n) { // find big gap in address space to map n bytes + void *A, *Amax = NULL; size_t L = 0, U, Max = 0, N = (size_t)n; char *r; + FYI("addrgap(%ld)\n", n); + if (N % (size_t)PGSZ) { ERR("file size %lu not multiple of PGSZ\n", N); SERN; } + if (N < sizeof(pma_hdr_t) + 10 * PGSZ) { ERR("file size %lu too small\n", N); SERN; } + for (U = 1; ; U *= 2) // double upper bound until failure + if (MAP_FAILED == (A = MMAP(U))) break; + else MUNMAP(A, U); + while (1 + L < U) { // binary search between bounds + size_t M = L + (U - L) / 2; // avoid overflow + if (MAP_FAILED == (A = MMAP(M))) { U = M; } + else { Amax = A; Max = M; MUNMAP(A, M); L = M; } + } + FYI("max gap: %lu bytes at %p\n", Max, Amax); + if (Max < N + (size_t)PGSZ * 2) { // safety margin + ERR("max gap %lu too small for required %lu\n", Max, N); + SERN; + } + r = (char *)Amax + (Max - N)/2; + while ((uintptr_t)r % PGSZ) // page align + r++; + FYI("addrgap returns %p == %lu\n", VS r, (uintptr_t)r); + return r; +} +#undef MMAP +#undef MUNMAP + +#define MM(a,s,f) mmap((a), (size_t)(s), PROT_READ | PROT_WRITE, MAP_SHARED, (f), 0) +int pma_init(int verbose, const char *file) { + int fd; void *a1, *a2; size_t as = sizeof(a1); struct stat s; + pma_hdr_t *h; + assert(0 <= verbose && 3 >= verbose); + state.vrb = verbose; + if (state.init) { ERR("already initialized\n"); assert(0); SERL; } + FYI("pma software version \"%s\" header version \"%s\", expects backing file format version %d\n", + pma_version, PMA_H_VERSION, VERS); + assert(0 == strcmp(pma_version, PMA_H_VERSION)); + FYI("pma_init(%d,\"%s\")\n", verbose, file); + // check assumptions + assert(WDSZ == sizeof(void *)); // in C11 we'd static_assert() + assert(WDSZ == sizeof(size_t)); + assert(WDSZ == sizeof(unsigned long)); + assert(0 == sizeof(pma_hdr_t) % WDSZ); + + PGSZ = sysconf(_SC_PAGESIZE); + if (NULL == file) { + WRN("no backing file provided; falling back on standard malloc\n"); + state.init = 2; + state.file = NULL; + state.hdr = NULL; + return 0; + } + // map backing file containing persistent heap + if (0 > (fd = open(file, O_RDWR))) { ERR("open()" ERN); SERL; } + if (0 != fstat(fd, &s)) { ERR("fstat()" ERN); SERL; } + if (!S_ISREG(s.st_mode)) { ERR("not reg\n" ); SERL; } + if ((ssize_t)as != read(fd, &a1, as)) { ERR("read()" ERN); SERL; } + if (NULL == a1) a1 = addrgap(s.st_size); + if (NULL == a1) { ERR("addrgap()" ERN); RL; } + FYI("map at %p\n", a1); + if (a1 != (a2 = MM(a1, s.st_size, fd))) { ERR("mmap()" ERN); SERL; } + if (0 != close(fd)) { ERR("close()" ERN); SE; } // carry on + state.init = 1; + state.file = file; + state.hdr = h = (pma_hdr_t *)a2; + if (NULL == h->mapaddr) { + int i; + ao_t *w, **ftr; // initial "wilderness", footer + FYI("initializing persistent heap\n"); + assert( 0 == h->bf_vers + && 0 == h->nallocs + && 0 == h->nfrees + && 0 == h->res_0 + && NULL == h->root + && NULL == h->afirst + && NULL == h->abound); + for (i = 0; i < NFL; i++) { + assert( NULL == h->free[i].anext + && NULL == h->free[i].fprev + && NULL == h->free[i].fnext); + // free[i] is dummy node in doubly-linked free list; this simplifies code to splice aos into & out of free list + h->free[i].fprev = h->free[i].fnext = &(h->free[i]); + } + h->mapaddr = h; + h->bf_vers = VERS; + h->nallocs = 0; + h->nfrees = 0; + h->res_0 = 0; + h->afirst = (ao_t *)(1 + h); + h->abound = (ao_t *)((char *)h + s.st_size); // TODO: squelch alignment warning? + // install "wilderness" free ao on all-object list; every free ao has a + // footer pointing to its header, to facilitate coalescing adjacent frees; + // header on final ao points beyond allocatable area + w = h->afirst; + w->anext = h->abound; + assert(0 == AOSZ(w) % WDSZ && WDSZ < AOSZ(w)); + ftr = (ao_t **)h->abound - 1; + *ftr = w; + fli(w); + } + else { + FYI("persistent heap already initialized\n"); + if (VERS != h->bf_vers) { + ERR("backing file version mismatch: %d vs. %" PRIu64 "\n", VERS, h->bf_vers); + SERL; + } + (void)sc(1); // to populate UB[] + } + if (IC) { ERR("integrity check failed\n"); SERL; } + return 0; +} +#undef MM + +// bite off adequate prefix if ao is too large, return remainder to appropriate +// free list; must handle two cases: given ao is free, versus given ao is live +// and is being shrunk by realloc +static ao_t * split_ao(ao_t *p, size_t s) { + size_t c = AOCAP(p), Cw = c / WDSZ, Sw; int iu, piu, grown; ao_t *n; + if (s < 24) s = 24; // increase request size to minimum allocation size if necessary; TODO: magic number here + Sw = s / WDSZ + !!(s % WDSZ); + assert(NULL == LOBH(p)); // lo bits of header (p->anext) might be set, but not lo bits of p + assert(NULL == p->fprev && NULL == p->fnext); // *p should already be spliced out of free lists + assert(c >= s && 0 == c % WDSZ); + FYI("split_ao(%p,%lu) AOCAP %lu words req %lu words cap %lu\n", VS p, s, c, Sw, Cw); + globh(p, &iu, &piu, &grown); + if (4 <= Cw - Sw) { // split ao if remainder is large enough to be allocatable + ao_t *rem = (ao_t *)(&(p->fprev) + Sw), // remainder + **rft = (ao_t **)HIBH(p->anext) - 1; // footer of remainder + FYI("splitting at %p\n", VS rem); + rem->anext = HIBH(p->anext); // set header of remainder + *rft = rem; // set footer of remainder + fli(rem); + p->anext = rem; // set header of *p + } + assert(AOCAP(p) >= s); + slobh(p, 1, piu, grown); // in-use bit is set; values of prev-in-use and grown bits are preserved + // set prev-in-use bit of next ao on anext list (if such exists), preserving iu and grown bits + n = HIBH(p->anext); + assert(n <= state.hdr->abound); + if (n < state.hdr->abound) { + globh(n, &iu, &piu, &grown); + slobh(n, iu, 1, grown); + } + return p; +} + +void * pma_malloc(size_t size) { + ao_t *r = NULL; + FYI("malloc(%lu)\n", size); + ASI; + if (2 == state.init) return malloc(size); + assert(!IC); + if (0 >= size) { + WRN("malloc(%lu) argument <= zero\n", size); SERN; } + for (int c = sc(size); c < NFL; c++) { + ao_t *h = &(state.hdr->free[c]); + // FYI("check size class %d UB %lu\n", c, UB[c]); + for (ao_t *f = h->fnext; f != h; f = f->fnext) { + // FYI("free list contains ao with capacity %lu\n", AOCAP(f)); + if (AOCAP(f) >= size) { + r = f; + goto end; + } + } + } + end: + if (NULL != r) { + flr(r); + r = split_ao(r, size); + FYI("malloc returning %p\n", VS &(r->fprev)); + ++(state.hdr->nallocs); + assert(!IC); + return &(r->fprev); + } + else { + WRN("malloc(%lu) cannot satisfy request at this time\n", size); + SERN; // conflates ENOMEM / EAGAIN (request might succeed after frees) + } +} + +void * pma_calloc(size_t nmemb, size_t size) { + void *p; + FYI("calloc(%lu,%lu)\n", nmemb, size); + ASI; + if (2 == state.init) return calloc(nmemb, size); + if (0 >= nmemb || 0 >= size) { + WRN("calloc(%lu,%lu) argument <= zero\n", nmemb, size); SERN; } + // SSIZE_MAX exists but SIZE_MAX apparently doesn't; sheesh + if (nmemb > UINT64_MAX / size) { + WRN("calloc(%lu,%lu) arguments overflow\n", nmemb, size); SERN; } + if (NULL != (p = pma_malloc(nmemb * size))) + (void)memset(p, 0, nmemb * size); + return p; +} + +void * pma_realloc(void *ptr, size_t size) { + ao_t *p; void *nu; // "new" is a C++ keyword + FYI("realloc(%p,%lu)\n", ptr, size); + ASI; + if (2 == state.init) return realloc(ptr, size); + if (NULL == ptr) return pma_malloc(size); + if (0 >= size) { pma_free(ptr); RN; } + p = (ao_t *)((ao_t **)ptr - 1); + if (AOCAP(p) >= size) // no growth needed + return ptr; + nu = pma_malloc(size); + if (NULL == nu) + SERN; + (void)memcpy(nu, ptr, AOCAP(p)); + pma_free(ptr); + return nu; +} + +// Merge *p with next ao on anext list; returns 1 if coalesces, 0 otherwise. +// Flag indicates which of the two aos is on the free list and must be removed. +static int coalesce(ao_t *p, int flr_lo_hi) { + ao_t *n = HIBH(p->anext), **ftr; int piu; + assert(n > p && n <= state.hdr->abound); + FYI("coalesce(%p)\n", VS p); + if (n >= state.hdr->abound) // *p is final ao on anext list + return 0; + if (0 == getbit(n, IU)) { // next ao is not in use, therefore coalesce + flr(flr_lo_hi ? n : p); // remove appropriate ao from free list + piu = getbit(p, PIU); + p->anext = HIBH(n->anext); + ftr = (ao_t **)p->anext - 1; + *ftr = p; + slobh(p, 0, piu, 0); // preserve prev-in-use bit of header of *p + return 1; + } + else // next ao is in use, therefore do not coalesce + return 0; +} + +void pma_free(void *ptr) { + ao_t *p, *n, **ftr; int r; + FYI("free(%p)\n", ptr); + ASI; + if (2 == state.init) { free(ptr); return; } + assert(!IC); + if (NULL == ptr) return; // allowed by C & POSIX + if (! (VS state.hdr->afirst <= ptr && VS state.hdr->abound > ptr)) { // e.g., p=strdup("foo") ... pma_free(p); + ERR("freed ptr %p outside allocatable area bounds %p %p\n", + ptr, VS state.hdr->afirst, VS state.hdr->abound); + assert(0); + SE; + return; + } + assert(0 == (uintptr_t)ptr % WDSZ); + p = (ao_t *)((ao_t **)ptr - 1); + assert(VAO(p)); + n = HIBH(p->anext); + assert(p < n && n <= state.hdr->abound); + assert(1 == getbit(p, IU)); + slobh(p, 0, getbit(p, PIU), 0); // clear iu and grown bits of *p header + if (n < state.hdr->abound) + assert(1 == getbit(n, PIU)); + FYI("merge with right/higher ao\n"); + r = coalesce(p, 1); + FYI("%s\n", r ? "yes" : "no"); + if (0 == getbit(p, PIU) && p > state.hdr->afirst) { // if ao is not leftmost/lowest and previous/lower ao is not in use, merge + ao_t *prev = *((ao_t **)p - 1); + assert(prev < p); + FYI("merge with left/lower ao\n"); + r = coalesce(prev, 0); + assert(r); + p = prev; + } +#ifndef NDEBUG + (void)memset(&(p->fprev), 0, AOCAP(p)); // for near-complete "reversibility" +#endif + n = HIBH(p->anext); + assert(p < n && n <= state.hdr->abound); + ftr = (ao_t **)n - 1; + *ftr = p; + if (n < state.hdr->abound) + slobh(n, getbit(n, IU), 0, getbit(n, GROWN)); // clear prev-in-use bit of next + fli(p); + ++(state.hdr->nfrees); + assert(!IC); + } + +void pma_set_root(void *p) { + FYI("set_root(%p)\n", p); + ASI; + if (2 == state.init) { ERR("set_root" NM); assert(0); SE; return; } + assert(NULL == p || VAO(p)); // could also check that p "looks like" pointer returned by malloc, + state.hdr->root = p; // e.g., header's in-use bit should be set and HIBH should be reasonable +} + +void * pma_get_root(void) { + void *p; + FYI("get_root()\n"); + ASI; + if (2 == state.init) { ERR("get_root" NM); assert(0); SERN; } + p = state.hdr->root; + assert(NULL == p || VAO(p)); + return p; +} + +typedef unsigned long ul_t; +void pma_set_avail_mem(const ul_t v) { + FYI("set_avail_mem(0x%lx)\n", v); + ASI; + if (2 == state.init) { ERR("set_avail_mem" NM); assert(0); SE; return; } + assert(!IC); + for (int i = 0; i < NFL; i++) { + ao_t *p, *f = &(state.hdr->free[i]); + if (f->fprev != f) + for (p = f->fnext; p != f; p = p->fnext) { + ul_t *q = (ul_t *)(1 + p), + *e = (ul_t *)(HIBH(p->anext)) - 1; + for ( ; q != e; q++) + if (*q != v) // avoid over-writing same value; gratuitous modification is a Bad Thing for persistent memory + *q = v; + for ( ; q != e; q++) + assert(*q == v); + } + } + assert(!IC); +} + diff --git a/support/pma.h b/support/pma.h new file mode 100644 index 00000000..f5851d96 --- /dev/null +++ b/support/pma.h @@ -0,0 +1,73 @@ +/* "pma", a persistent memory allocator (interface) + Copyright (C) 2022 Terence Kelly + Contact: tpkelly @ { acm.org, cs.princeton.edu, eecs.umich.edu } + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program 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 Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. +*/ + +#ifndef PMA_H_INCLUDED +#define PMA_H_INCLUDED + +// version strings of interface and implementation should match +#define PMA_H_VERSION "2022.05May.01 (Avon 5) + gawk" +extern const char pma_version[]; + +/* May contain line number in pma.c where something went wrong if one + of the other interfaces fails. "Use the Source, Luke." */ +extern int pma_errno; + +/* Must be called exactly once before any other pma_* function is + called, otherwise behavior is undefined. Available verbosity + levels are: 0 => no diagnostic printouts, 1 => errors only printed + to stderr, 2 => also warnings, 3 => also very verbose "FYI" + messages. Use verbosity level 2 by default. File argument + specifies backing file containing persistent heap, initially an + empty sparse file whose size is a multiple of the system page + size. If file argument is NULL, fall back on standard memory + allocator: pma_malloc passes the buck to ordinary malloc, pma_free + calls ordinary free, etc. In fallback-to-standard-malloc mode, + only pma_malloc/calloc/realloc/free may be used; other functions + such as pma_get/set_root must not be used. The implementation may + store a copy of the file argument, i.e., the pointer, so both this + pointer and the memory to which it points (*file) must not + change. */ +extern int pma_init(int verbose, const char *file); + +/* The following four functions may be used like their standard + counterparts. See notes on pma_init for fallback to standard + allocator. See notes on fork in README. */ +extern void * pma_malloc(size_t size); +extern void * pma_calloc(size_t nmemb, size_t size); +extern void * pma_realloc(void *ptr, size_t size); +extern void pma_free(void *ptr); + +/* The following two functions access the persistent heap's root + pointer, which must either be NULL or must point within a block of + persistent memory. If the pointer passed to pma_set_root is not a + pointer returned by pma_malloc/calloc/realloc, that is likely a + bug, though the implementation is not obliged to check for such + bugs. */ +extern void pma_set_root(void *ptr); +extern void * pma_get_root(void); + +/* Prints to stderr details of internal data structures, e.g., free + lists, and performs integrity checks, which may be very slow. */ +extern void pma_check_and_dump(void); + +/* Set non-metadata words of free blocks to given value. Useful for + debugging (v == 0xdeadDEADbeefBEEF) and for preparing backing file + to be re-sparsified with fallocate (v == 0x0). */ +extern void pma_set_avail_mem(const unsigned long v); + +#endif // PMA_H_INCLUDED |