X-Git-Url: http://repo.macrolet.net/gitweb/?a=blobdiff_plain;f=src%2Fcode%2Ftarget-package.lisp;h=2e5bef5dbad7e24e3cacb93d5f85b5520420321a;hb=bfb19d306581ac86feb4371846c4b9953d692dd8;hp=673d17039912c2a9c59f29f70d603862e29457e3;hpb=4898ef32c639b1c7f4ee13a5ba566ce6debd03e6;p=sbcl.git diff --git a/src/code/target-package.lisp b/src/code/target-package.lisp index 673d170..2e5bef5 100644 --- a/src/code/target-package.lisp +++ b/src/code/target-package.lisp @@ -39,24 +39,41 @@ (package-hashtable-free table) (package-hashtable-deleted table)))) -;;; the maximum density we allow in a package hashtable -(defconstant package-rehash-threshold 0.75) +;;; the maximum load factor we allow in a package hashtable +(defconstant +package-rehash-threshold+ 0.75) + +;;; the load factor desired for a package hashtable when writing a +;;; core image +(defconstant +package-hashtable-image-load-factor+ 0.5) + +;;; All destructive package modifications are serialized on this lock. +(defvar *package-lock*) + +(!cold-init-forms + (setf *package-lock* (sb!thread::make-spinlock :name "Package Lock"))) + +(defmacro with-packages ((&key) &body forms) + `(sb!thread::with-recursive-spinlock (*package-lock*) + ,@forms)) ;;; Make a package hashtable having a prime number of entries at least -;;; as great as (/ SIZE PACKAGE-REHASH-THRESHOLD). If RES is supplied, +;;; as great as (/ SIZE +PACKAGE-REHASH-THRESHOLD+). If RES is supplied, ;;; then it is destructively modified to produce the result. This is ;;; useful when changing the size, since there are many pointers to ;;; the hashtable. +;;; Actually, the smallest table built here has three entries. This +;;; is necessary because the double hashing step size is calculated +;;; using a division by the table size minus two. (defun make-or-remake-package-hashtable (size &optional res) (flet ((actual-package-hashtable-size (size) (loop for n of-type fixnum - from (logior (truncate size package-rehash-threshold) 1) + from (logior (ceiling size +package-rehash-threshold+) 1) by 2 when (positive-primep n) return n))) (let* ((n (actual-package-hashtable-size size)) - (size (truncate (* n package-rehash-threshold))) + (size (truncate (* n +package-rehash-threshold+))) (table (make-array n)) (hash (make-array n :element-type '(unsigned-byte 8) @@ -69,6 +86,17 @@ (package-hashtable-deleted res) 0) (setf res (%make-package-hashtable table hash size))) res))) + +;;; Destructively resize TABLE to have room for at least SIZE entries +;;; and rehash its existing entries. +(defun resize-package-hashtable (table size) + (let* ((vec (package-hashtable-table table)) + (hash (package-hashtable-hash table)) + (len (length vec))) + (make-or-remake-package-hashtable size table) + (dotimes (i len) + (when (> (aref hash i) 1) + (add-symbol table (svref vec i)))))) ;;;; package locking operations, built conditionally on :sb-package-locks @@ -357,7 +385,7 @@ error if any of PACKAGES is not a valid package designator." ;;; Make a package name into a simple-string. (defun package-namify (n) - (stringify-name n "package")) + (stringify-package-designator n)) ;;; ANSI specifies (in the definition of DELETE-PACKAGE) that PACKAGE-NAME ;;; returns NIL (not an error) for a deleted package, so this is a special @@ -386,33 +414,47 @@ error if any of PACKAGES is not a valid package designator." ;;; Add a symbol to a package hashtable. The symbol is assumed ;;; not to be present. (defun add-symbol (table symbol) + (when (zerop (package-hashtable-free table)) + ;; The hashtable is full. Resize it to be able to hold twice the + ;; amount of symbols than it currently contains. The actual new size + ;; can be smaller than twice the current size if the table contained + ;; deleted entries. + (resize-package-hashtable table + (* (- (package-hashtable-size table) + (package-hashtable-deleted table)) + 2))) (let* ((vec (package-hashtable-table table)) (hash (package-hashtable-hash table)) (len (length vec)) (sxhash (%sxhash-simple-string (symbol-name symbol))) - (h2 (the fixnum (1+ (the fixnum (rem sxhash - (the fixnum (- len 2)))))))) - (declare (fixnum len sxhash h2)) - (cond ((zerop (the fixnum (package-hashtable-free table))) - (make-or-remake-package-hashtable (* (package-hashtable-size table) - 2) - table) - (add-symbol table symbol) - (dotimes (i len) - (declare (fixnum i)) - (when (> (the fixnum (aref hash i)) 1) - (add-symbol table (svref vec i))))) - (t - (do ((i (rem sxhash len) (rem (+ i h2) len))) - ((< (the fixnum (aref hash i)) 2) - (if (zerop (the fixnum (aref hash i))) - (decf (package-hashtable-free table)) - (decf (package-hashtable-deleted table))) - (setf (svref vec i) symbol) - (setf (aref hash i) - (entry-hash (length (symbol-name symbol)) - sxhash))) - (declare (fixnum i))))))) + (h2 (1+ (rem sxhash (- len 2))))) + (declare (fixnum sxhash h2)) + (do ((i (rem sxhash len) (rem (+ i h2) len))) + ((< (the fixnum (aref hash i)) 2) + (if (zerop (the fixnum (aref hash i))) + (decf (package-hashtable-free table)) + (decf (package-hashtable-deleted table))) + (setf (svref vec i) symbol) + (setf (aref hash i) + (entry-hash (length (symbol-name symbol)) + sxhash))) + (declare (fixnum i))))) + +;;; Resize the package hashtables of all packages so that their load +;;; factor is +PACKAGE-HASHTABLE-IMAGE-LOAD-FACTOR+. Called from +;;; SAVE-LISP-AND-DIE to optimize space usage in the image. +(defun tune-hashtable-sizes-of-all-packages () + (flet ((tune-table-size (table) + (resize-package-hashtable + table + (round (* (/ +package-rehash-threshold+ + +package-hashtable-image-load-factor+) + (- (package-hashtable-size table) + (package-hashtable-free table) + (package-hashtable-deleted table))))))) + (dolist (package (list-all-packages)) + (tune-table-size (package-internal-symbols package)) + (tune-table-size (package-external-symbols package))))) ;;; Find where the symbol named STRING is stored in TABLE. INDEX-VAR ;;; is bound to the index, or NIL if it is not present. SYMBOL-VAR @@ -464,7 +506,17 @@ error if any of PACKAGES is not a valid package designator." (with-symbol (index symbol table string length hash ehash) (setf (aref (package-hashtable-hash table) index) 1) (setf (aref (package-hashtable-table table) index) nil) - (incf (package-hashtable-deleted table))))) + (incf (package-hashtable-deleted table)))) + ;; If the table is less than one quarter full, halve its size and + ;; rehash the entries. + (let* ((size (package-hashtable-size table)) + (deleted (package-hashtable-deleted table)) + (used (- size + (package-hashtable-free table) + deleted))) + (declare (type fixnum size deleted used)) + (when (< used (truncate size 4)) + (resize-package-hashtable table (* used 2))))) ;;; Enter any new NICKNAMES for PACKAGE into *PACKAGE-NAMES*. ;;; If there is a conflict then give the user a chance to do @@ -498,43 +550,41 @@ error if any of PACKAGES is not a valid package designator." (external-symbols 10)) #!+sb-doc #.(format nil - "Make a new package having the specified NAME, NICKNAMES, and - USE list. :INTERNAL-SYMBOLS and :EXTERNAL-SYMBOLS are - estimates for the number of internal and external symbols which - will ultimately be present in the package. The default value of - USE is implementation-dependent, and in this implementation - it is ~S." - *default-package-use-list*) - - ;; Check for package name conflicts in name and nicknames, then - ;; make the package. - (when (find-package name) - ;; ANSI specifies that this error is correctable. - (cerror "Leave existing package alone." - "A package named ~S already exists" name)) - (let* ((name (package-namify name)) - (package (internal-make-package - :%name name - :internal-symbols (make-or-remake-package-hashtable - internal-symbols) - :external-symbols (make-or-remake-package-hashtable - external-symbols)))) - - ;; Do a USE-PACKAGE for each thing in the USE list so that checking for - ;; conflicting exports among used packages is done. - (if *in-package-init* - (push (list use package) *!deferred-use-packages*) - (use-package use package)) - - ;; FIXME: ENTER-NEW-NICKNAMES can fail (ERROR) if nicknames are illegal, - ;; which would leave us with possibly-bad side effects from the earlier - ;; USE-PACKAGE (e.g. this package on the used-by lists of other packages, - ;; but not in *PACKAGE-NAMES*, and possibly import side effects too?). - ;; Perhaps this can be solved by just moving ENTER-NEW-NICKNAMES before - ;; USE-PACKAGE, but I need to check what kinds of errors can be caused by - ;; USE-PACKAGE, too. - (enter-new-nicknames package nicknames) - (setf (gethash name *package-names*) package))) + "Make a new package having the specified NAME, NICKNAMES, and USE +list. :INTERNAL-SYMBOLS and :EXTERNAL-SYMBOLS are estimates for the number of +internal and external symbols which will ultimately be present in the package. +The default value of USE is implementation-dependent, and in this +implementation it is ~S." *default-package-use-list*) + (with-packages () + ;; Check for package name conflicts in name and nicknames, then + ;; make the package. + (when (find-package name) + ;; ANSI specifies that this error is correctable. + (cerror "Leave existing package alone." + "A package named ~S already exists" name)) + (let* ((name (package-namify name)) + (package (internal-make-package + :%name name + :internal-symbols (make-or-remake-package-hashtable + internal-symbols) + :external-symbols (make-or-remake-package-hashtable + external-symbols)))) + + ;; Do a USE-PACKAGE for each thing in the USE list so that checking for + ;; conflicting exports among used packages is done. + (if *in-package-init* + (push (list use package) *!deferred-use-packages*) + (use-package use package)) + + ;; FIXME: ENTER-NEW-NICKNAMES can fail (ERROR) if nicknames are illegal, + ;; which would leave us with possibly-bad side effects from the earlier + ;; USE-PACKAGE (e.g. this package on the used-by lists of other packages, + ;; but not in *PACKAGE-NAMES*, and possibly import side effects too?). + ;; Perhaps this can be solved by just moving ENTER-NEW-NICKNAMES before + ;; USE-PACKAGE, but I need to check what kinds of errors can be caused by + ;; USE-PACKAGE, too. + (enter-new-nicknames package nicknames) + (setf (gethash name *package-names*) package)))) ;;; Change the name if we can, blast any old nicknames and then ;;; add in any new ones. @@ -548,91 +598,93 @@ error if any of PACKAGES is not a valid package designator." (defun rename-package (package name &optional (nicknames ())) #!+sb-doc "Changes the name and nicknames for a package." - (let* ((package (find-undeleted-package-or-lose package)) - (name (package-namify name)) - (found (find-package name)) - (nicks (mapcar #'string nicknames))) - (unless (or (not found) (eq found package)) - (error 'simple-package-error - :package name - :format-control "A package named ~S already exists." - :format-arguments (list name))) - (with-single-package-locked-error () + (with-packages () + (let* ((package (find-undeleted-package-or-lose package)) + (name (package-namify name)) + (found (find-package name)) + (nicks (mapcar #'string nicknames))) + (unless (or (not found) (eq found package)) + (error 'simple-package-error + :package name + :format-control "A package named ~S already exists." + :format-arguments (list name))) + (with-single-package-locked-error () (unless (and (string= name (package-name package)) (null (set-difference nicks (package-nicknames package) - :test #'string=))) + :test #'string=))) (assert-package-unlocked package "rename as ~A~@[ with nickname~P ~ ~{~A~^, ~}~]" name (length nicks) nicks)) - ;; do the renaming - (remhash (package-%name package) *package-names*) - (dolist (n (package-%nicknames package)) - (remhash n *package-names*)) - (setf (package-%name package) name - (gethash name *package-names*) package - (package-%nicknames package) ()) - (enter-new-nicknames package nicknames)) - package)) + ;; do the renaming + (remhash (package-%name package) *package-names*) + (dolist (n (package-%nicknames package)) + (remhash n *package-names*)) + (setf (package-%name package) name + (gethash name *package-names*) package + (package-%nicknames package) ()) + (enter-new-nicknames package nicknames)) + package))) (defun delete-package (package-designator) #!+sb-doc "Delete the package designated by PACKAGE-DESIGNATOR from the package system data structures." - (let ((package (if (packagep package-designator) - package-designator - (find-package package-designator)))) - (cond ((not package) - ;; This continuable error is required by ANSI. - (cerror - "Return ~S." - (make-condition - 'simple-package-error - :package package-designator - :format-control "There is no package named ~S." - :format-arguments (list package-designator)) - nil)) - ((not (package-name package)) ; already deleted - nil) - (t - (with-single-package-locked-error - (:package package "deleting package ~A" package) - (let ((use-list (package-used-by-list package))) - (when use-list - ;; This continuable error is specified by ANSI. - (cerror - "Remove dependency in other packages." - (make-condition - 'simple-package-error - :package package - :format-control - "~@" - :format-arguments (list (package-name package) - (length use-list) - (mapcar #'package-name use-list)))) - (dolist (p use-list) - (unuse-package package p)))) - (dolist (used (package-use-list package)) - (unuse-package used package)) - (do-symbols (sym package) - (unintern sym package)) - (remhash (package-name package) *package-names*) - (dolist (nick (package-nicknames package)) - (remhash nick *package-names*)) - (setf (package-%name package) nil - ;; Setting PACKAGE-%NAME to NIL is required in order to - ;; make PACKAGE-NAME return NIL for a deleted package as - ;; ANSI requires. Setting the other slots to NIL - ;; and blowing away the PACKAGE-HASHTABLES is just done - ;; for tidiness and to help the GC. - (package-%nicknames package) nil - (package-%use-list package) nil - (package-tables package) nil - (package-%shadowing-symbols package) nil - (package-internal-symbols package) - (make-or-remake-package-hashtable 0) - (package-external-symbols package) - (make-or-remake-package-hashtable 0)) - t))))) + (with-packages () + (let ((package (if (packagep package-designator) + package-designator + (find-package package-designator)))) + (cond ((not package) + ;; This continuable error is required by ANSI. + (cerror + "Return ~S." + (make-condition + 'simple-package-error + :package package-designator + :format-control "There is no package named ~S." + :format-arguments (list package-designator)) + nil)) + ((not (package-name package)) ; already deleted + nil) + (t + (with-single-package-locked-error + (:package package "deleting package ~A" package) + (let ((use-list (package-used-by-list package))) + (when use-list + ;; This continuable error is specified by ANSI. + (cerror + "Remove dependency in other packages." + (make-condition + 'simple-package-error + :package package + :format-control + "~@" + :format-arguments (list (package-name package) + (length use-list) + (mapcar #'package-name use-list)))) + (dolist (p use-list) + (unuse-package package p)))) + (dolist (used (package-use-list package)) + (unuse-package used package)) + (do-symbols (sym package) + (unintern sym package)) + (remhash (package-name package) *package-names*) + (dolist (nick (package-nicknames package)) + (remhash nick *package-names*)) + (setf (package-%name package) nil + ;; Setting PACKAGE-%NAME to NIL is required in order to + ;; make PACKAGE-NAME return NIL for a deleted package as + ;; ANSI requires. Setting the other slots to NIL + ;; and blowing away the PACKAGE-HASHTABLES is just done + ;; for tidiness and to help the GC. + (package-%nicknames package) nil + (package-%use-list package) nil + (package-tables package) nil + (package-%shadowing-symbols package) nil + (package-internal-symbols package) + (make-or-remake-package-hashtable 0) + (package-external-symbols package) + (make-or-remake-package-hashtable 0)) + t)))))) (defun list-all-packages () #!+sb-doc @@ -681,21 +733,29 @@ error if any of PACKAGES is not a valid package designator." (cond (where (values symbol where)) (t - (let ((symbol-name (subseq name 0 length))) - (with-single-package-locked-error - (:package package "interning ~A" symbol-name) - (let ((symbol (make-symbol symbol-name))) - (%set-symbol-package symbol package) - (cond ((eq package *keyword-package*) - (add-symbol (package-external-symbols package) symbol) - (%set-symbol-value symbol symbol)) - (t - (add-symbol (package-internal-symbols package) symbol))) - (values symbol nil)))))))) + ;; Let's try again with a lock: the common case has the + ;; symbol already interned, handled by the first leg of the + ;; COND, but in case another thread is interning in + ;; parallel we need to check after grabbing the lock. + (with-packages () + (setf (values symbol where) (find-symbol* name length package)) + (if where + (values symbol where) + (let ((symbol-name (subseq name 0 length))) + (with-single-package-locked-error + (:package package "interning ~A" symbol-name) + (let ((symbol (make-symbol symbol-name))) + (%set-symbol-package symbol package) + (cond + ((eq package *keyword-package*) + (add-symbol (package-external-symbols package) symbol) + (%set-symbol-value symbol symbol)) + (t + (add-symbol (package-internal-symbols package) symbol))) + (values symbol nil)))))))))) ;;; Check internal and external symbols, then scan down the list -;;; of hashtables for inherited symbols. When an inherited symbol -;;; is found pull that table to the beginning of the list. +;;; of hashtables for inherited symbols. (defun find-symbol* (string length package) (declare (simple-string string) (type index length)) @@ -716,8 +776,20 @@ error if any of PACKAGES is not a valid package designator." ((null table) (values nil nil)) (with-symbol (found symbol (car table) string length hash ehash) (when found - (unless (eq prev head) - (shiftf (cdr prev) (cdr table) (cdr head) table)) + ;; At this point we used to move the table to the + ;; beginning of the list, probably on the theory that we'd + ;; soon be looking up further items there. Unfortunately + ;; that was very much non-thread safe. Since the failure + ;; mode was nasty (corruption of the package in a way + ;; which would make symbol lookups loop infinitely) and it + ;; would be triggered just by doing reads to a resource + ;; that users can't do their own locking on, that code has + ;; been removed. If we ever add locking to packages, + ;; resurrecting that code might make sense, even though it + ;; didn't seem to have much of an performance effect in + ;; normal use. + ;; + ;; -- JES, 2006-09-13 (return-from find-symbol* (values symbol :inherited)))))))) ;;; Similar to FIND-SYMBOL, but only looks for an external symbol. @@ -733,6 +805,17 @@ error if any of PACKAGES is not a valid package designator." string length hash ehash) (values symbol found)))) +(defun print-symbol-with-prefix (stream symbol colon at) + #!+sb-doc + "For use with ~/: Write SYMBOL to STREAM as if it is not accessible from + the current package." + (declare (ignore colon at)) + ;; Only keywords should be accessible from the keyword package, and + ;; keywords are always printed with colons, so this guarantees that the + ;; symbol will not be printed without a prefix. + (let ((*package* *keyword-package*)) + (write symbol :stream stream :escape t))) + (define-condition name-conflict (reference-condition package-error) ((function :initarg :function :reader name-conflict-function) (datum :initarg :datum :reader name-conflict-datum) @@ -741,7 +824,8 @@ error if any of PACKAGES is not a valid package designator." (:report (lambda (c s) (format s "~@<~S ~S causes name-conflicts in ~S between the ~ - following symbols:~2I~@:_~{~S~^, ~}~:@>" + following symbols:~2I~@:_~ + ~{~/sb-impl::print-symbol-with-prefix/~^, ~}~:@>" (name-conflict-function c) (name-conflict-datum c) (package-error-package c) @@ -756,9 +840,12 @@ error if any of PACKAGES is not a valid package designator." :interactive (lambda () (let* ((len (length symbols)) - (nlen (length (write-to-string len :base 10)))) + (nlen (length (write-to-string len :base 10))) + (*print-pretty* t)) (format *query-io* "~&~@