(def %array-available-elements)
(def %array-data-vector)
(def %array-displacement)
- (def %array-displaced-p))
+ (def %array-displaced-p)
+ (def %array-diplaced-from))
(defun %array-rank (array)
(%array-rank array))
(setf (%array-fill-pointer-p array) nil)))
(setf (%array-available-elements array) total-size)
(setf (%array-data-vector array) data)
+ (setf (%array-displaced-from array) nil)
(cond (displaced-to
(when (or initial-element-p initial-contents-p)
(error "Neither :INITIAL-ELEMENT nor :INITIAL-CONTENTS ~
(array-total-size displaced-to))
(error "~S doesn't have enough elements." displaced-to))
(setf (%array-displacement array) offset)
- (setf (%array-displaced-p array) t)))
+ (setf (%array-displaced-p array) t)
+ (%save-displaced-array-backpointer array data)))
(t
(setf (%array-displaced-p array) nil)))
(let ((axis 0))
;;; vectors or not simple.
(macrolet ((def (name table-name)
`(progn
- (defvar ,table-name)
+ (defglobal ,table-name (make-array ,(1+ sb!vm:widetag-mask)))
(defmacro ,name (array-var)
- `(the function
- (let ((tag 0)
- (offset
- #.(ecase sb!c:*backend-byte-order*
- (:little-endian
- (- sb!vm:other-pointer-lowtag))
- (:big-endian
- (- (1- sb!vm:n-word-bytes) sb!vm:other-pointer-lowtag)))))
- ;; WIDETAG-OF needs extra code to handle LIST and
- ;; FUNCTION lowtags. We're only dispatching on
- ;; other pointers, so let's do the lowtag
- ;; extraction manually.
- (when (sb!vm::%other-pointer-p ,array-var)
- (setf tag
- (sb!sys:sap-ref-8 (int-sap (get-lisp-obj-address ,array-var))
- offset)))
- ;; SYMBOL-GLOBAL-VALUE is a performance hack
- ;; for threaded builds.
- (svref (sb!vm::symbol-global-value ',',table-name) tag)))))))
- (def !find-data-vector-setter *data-vector-setters*)
- (def !find-data-vector-setter/check-bounds *data-vector-setters/check-bounds*)
- (def !find-data-vector-reffer *data-vector-reffers*)
- (def !find-data-vector-reffer/check-bounds *data-vector-reffers/check-bounds*))
+ `(the function
+ (let ((tag 0))
+ (when (sb!vm::%other-pointer-p ,array-var)
+ (setf tag (%other-pointer-widetag ,array-var)))
+ (svref ,',table-name tag)))))))
+ (def !find-data-vector-setter %%data-vector-setters%%)
+ (def !find-data-vector-setter/check-bounds %%data-vector-setters/check-bounds%%)
+ (def !find-data-vector-reffer %%data-vector-reffers%%)
+ (def !find-data-vector-reffer/check-bounds %%data-vector-reffers/check-bounds%%))
(macrolet ((%ref (accessor-getter extra-params)
`(funcall (,accessor-getter array) array index ,@extra-params))
new-value)))
(define-reffers (symbol deffer check-form slow-path)
`(progn
- (setf ,symbol (make-array sb!vm::widetag-mask
+ ;; FIXME/KLUDGE: can't just FILL here, because genesis doesn't
+ ;; preserve the binding, so re-initiaize as NS doesn't have
+ ;; the energy to figure out to change that right now.
+ (setf ,symbol (make-array (1+ sb!vm::widetag-mask)
:initial-element #'hairy-ref-error))
,@(loop for widetag in '(sb!vm:complex-vector-widetag
sb!vm:complex-vector-nil-widetag
collect `(setf (svref ,symbol ,widetag)
(,deffer ,saetp ,check-form))))))
(defun !hairy-data-vector-reffer-init ()
- (define-reffers *data-vector-reffers* define-reffer
+ (define-reffers %%data-vector-reffers%% define-reffer
(progn)
#'slow-hairy-data-vector-ref)
- (define-reffers *data-vector-setters* define-setter
+ (define-reffers %%data-vector-setters%% define-setter
(progn)
#'slow-hairy-data-vector-set)
- (define-reffers *data-vector-reffers/check-bounds* define-reffer
+ (define-reffers %%data-vector-reffers/check-bounds%% define-reffer
(%check-bound vector (length vector))
#'slow-hairy-data-vector-ref/check-bounds)
- (define-reffers *data-vector-setters/check-bounds* define-setter
+ (define-reffers %%data-vector-setters/check-bounds%% define-setter
(%check-bound vector (length vector))
#'slow-hairy-data-vector-set/check-bounds)))
(defun data-vector-ref-with-offset (array index offset)
(hairy-data-vector-ref array (+ index offset)))
+(defun invalid-array-p (array)
+ (and (array-header-p array)
+ (consp (%array-displaced-p array))))
+
+(declaim (ftype (function (array) nil) invalid-array-error))
+(defun invalid-array-error (array)
+ (aver (array-header-p array))
+ ;; Array invalidation stashes the original dimensions here...
+ (let ((dims (%array-displaced-p array))
+ (et (array-element-type array)))
+ (error 'invalid-array-error
+ :datum array
+ :expected-type
+ (if (cdr dims)
+ `(array ,et ,dims)
+ `(vector ,et ,@dims)))))
+
+(declaim (ftype (function (array integer integer &optional t) nil)
+ invalid-array-index-error))
+(defun invalid-array-index-error (array index bound &optional axis)
+ (if (invalid-array-p array)
+ (invalid-array-error array)
+ (error 'invalid-array-index-error
+ :array array
+ :axis axis
+ :datum index
+ :expected-type `(integer 0 (,bound)))))
+
;;; SUBSCRIPTS has a dynamic-extent list structure and is destroyed
(defun %array-row-major-index (array subscripts
&optional (invalid-index-error-p t))
(declare (fixnum dim))
(unless (and (fixnump index) (< -1 index dim))
(if invalid-index-error-p
- (error 'simple-type-error
- :format-control "invalid index ~W~[~;~:; on axis ~:*~W~] in ~S"
- :format-arguments (list index axis array)
- :datum index
- :expected-type `(integer 0 (,dim)))
+ (invalid-array-index-error array index dim axis)
(return-from %array-row-major-index nil)))
(incf result (* chunk-size (the fixnum index)))
(setf chunk-size (* chunk-size dim))))
(length (length (the (simple-array * (*)) array))))
(unless (and (fixnump index) (< -1 index length))
(if invalid-index-error-p
- ;; FIXME: perhaps this should share a format-string
- ;; with INVALID-ARRAY-INDEX-ERROR or
- ;; INDEX-TOO-LARGE-ERROR?
- (error 'simple-type-error
- :format-control "invalid index ~W in ~S"
- :format-arguments (list index array)
- :datum index
- :expected-type `(integer 0 (,length)))
+ (invalid-array-index-error array index length)
(return-from %array-row-major-index nil)))
index))))
(defun array-in-bounds-p (array &rest subscripts)
#!+sb-doc
- "Return T if the SUBSCIPTS are in bounds for the ARRAY, NIL otherwise."
+ "Return T if the SUBSCRIPTS are in bounds for the ARRAY, NIL otherwise."
(if (%array-row-major-index array subscripts nil)
t))
(error "Axis number ~W is too big; ~S only has ~D dimension~:P."
axis-number array (%array-rank array)))
(t
- ;; ANSI sayeth (ADJUST-ARRAY dictionary entry):
- ;;
- ;; "If A is displaced to B, the consequences are
- ;; unspecified if B is adjusted in such a way that it no
- ;; longer has enough elements to satisfy A.
- ;;
- ;; In situations where this matters we should be doing a
- ;; bounds-check, which in turn uses ARRAY-DIMENSION -- so
- ;; this seems like a good place to signal an error.
- (multiple-value-bind (target offset) (array-displacement array)
- (when (and target
- (> (array-total-size array)
- (- (array-total-size target) offset)))
- (error 'displaced-to-array-too-small-error
- :format-control "~@<The displaced-to array is too small. ~S ~
- elements after offset required, ~S available.~:@>"
- :format-arguments (list (array-total-size array)
- (- (array-total-size target) offset))))
- (%array-dimension array axis-number)))))
+ (%array-dimension array axis-number))))
(defun array-dimensions (array)
#!+sb-doc
:datum arg
:expected-type (list 'integer 0 max)
:format-control "The new fill pointer, ~S, is larger than the length of the vector (~S.)"
- arg max)))
+ :format-arguments (list arg max))))
(t
(error 'simple-type-error
:datum vector
displaced-to displaced-index-offset)
#!+sb-doc
"Adjust ARRAY's dimensions to the given DIMENSIONS and stuff."
+ (when (invalid-array-p array)
+ (invalid-array-error array))
(let ((dimensions (if (listp dimensions) dimensions (list dimensions))))
(cond ((/= (the fixnum (length (the list dimensions)))
(the fixnum (array-rank array)))
(set-array-header array array-data array-size
(get-new-fill-pointer array array-size
fill-pointer)
- 0 dimensions nil)
+ 0 dimensions nil nil)
(if (array-header-p array)
;; simple multidimensional or single dimensional array
(make-array dimensions
(set-array-header array displaced-to array-size
(get-new-fill-pointer array array-size
fill-pointer)
- displacement dimensions t)
+ displacement dimensions t nil)
;; simple multidimensional or single dimensional array
(make-array dimensions
:element-type element-type
(set-array-header array new-data new-length
(get-new-fill-pointer array new-length
fill-pointer)
- 0 dimensions nil)
+ 0 dimensions nil nil)
new-data))))
(t
(let ((old-length (%array-available-elements array))
initial-element-p))
(if (adjustable-array-p array)
(set-array-header array new-data new-length
- new-length 0 dimensions nil)
+ nil 0 dimensions nil nil)
(let ((new-array
(make-array-header
sb!vm:simple-array-widetag array-rank)))
(set-array-header new-array new-data new-length
- new-length 0 dimensions nil)))))))))))
+ nil 0 dimensions nil t)))))))))))
(defun get-new-fill-pointer (old-array new-array-size fill-pointer)
vector)
(t (subseq vector 0 new-length))))
+;;; BIG THREAD SAFETY NOTE
+;;;
+;;; ADJUST-ARRAY/SET-ARRAY-HEADER, and its callees are very
+;;; thread unsafe. They are nonatomic, and can mess with parallel
+;;; code using the same arrays.
+;;;
+;;; A likely seeming fix is an additional level of indirection:
+;;; ARRAY-HEADER -> ARRAY-INFO -> ... where ARRAY-HEADER would
+;;; hold nothing but the pointer to ARRAY-INFO, and ARRAY-INFO
+;;; would hold everything ARRAY-HEADER now holds. This allows
+;;; consing up a new ARRAY-INFO and replacing it atomically in
+;;; the ARRAY-HEADER.
+;;;
+;;; %WALK-DISPLACED-ARRAY-BACKPOINTERS is an especially nasty
+;;; one: not only is it needed extremely rarely, which makes
+;;; any thread safety bugs involving it look like rare random
+;;; corruption, but because it walks the chain *upwards*, which
+;;; may violate user expectations.
+
+(defun %save-displaced-array-backpointer (array data)
+ (flet ((purge (pointers)
+ (remove-if (lambda (value)
+ (or (not value) (eq array value)))
+ pointers
+ :key #'weak-pointer-value)))
+ ;; Add backpointer to the new data vector if it has a header.
+ (when (array-header-p data)
+ (setf (%array-displaced-from data)
+ (cons (make-weak-pointer array)
+ (purge (%array-displaced-from data)))))
+ ;; Remove old backpointer, if any.
+ (let ((old-data (%array-data-vector array)))
+ (when (and (neq data old-data) (array-header-p old-data))
+ (setf (%array-displaced-from old-data)
+ (purge (%array-displaced-from old-data)))))))
+
+(defun %walk-displaced-array-backpointers (array new-length)
+ (dolist (p (%array-displaced-from array))
+ (let ((from (weak-pointer-value p)))
+ (when (and from (eq array (%array-data-vector from)))
+ (let ((requires (+ (%array-available-elements from)
+ (%array-displacement from))))
+ (unless (>= new-length requires)
+ ;; ANSI sayeth (ADJUST-ARRAY dictionary entry):
+ ;;
+ ;; "If A is displaced to B, the consequences are unspecified if B is
+ ;; adjusted in such a way that it no longer has enough elements to
+ ;; satisfy A.
+ ;;
+ ;; since we're hanging on a weak pointer here, we can't signal an
+ ;; error right now: the array that we're looking at might be
+ ;; garbage. Instead, we set all dimensions to zero so that next
+ ;; safe access to the displaced array will trap. Additionally, we
+ ;; save the original dimensions, so we can signal a more
+ ;; understandable error when the time comes.
+ (%walk-displaced-array-backpointers from 0)
+ (setf (%array-fill-pointer from) 0
+ (%array-available-elements from) 0
+ (%array-displaced-p from) (array-dimensions array))
+ (dotimes (i (%array-rank from))
+ (setf (%array-dimension from i) 0))))))))
+
;;; Fill in array header with the provided information, and return the array.
(defun set-array-header (array data length fill-pointer displacement dimensions
- &optional displacedp)
+ displacedp newp)
+ (if newp
+ (setf (%array-displaced-from array) nil)
+ (%walk-displaced-array-backpointers array length))
+ (when displacedp
+ (%save-displaced-array-backpointer array data))
(setf (%array-data-vector array) data)
(setf (%array-available-elements array) length)
(cond (fill-pointer
(setf (%array-dimension array 0) dimensions))
(setf (%array-displaced-p array) displacedp)
array)
+
+;;; User visible extension
+(declaim (ftype (function (array) (values (simple-array * (*)) &optional))
+ array-storage-vector))
+(defun array-storage-vector (array)
+ "Returns the underlying storage vector of ARRAY, which must be a non-displaced array.
+
+In SBCL, if ARRAY is a of type \(SIMPLE-ARRAY * \(*)), it is its own storage
+vector. Multidimensional arrays, arrays with fill pointers, and adjustable
+arrays have an underlying storage vector with the same ARRAY-ELEMENT-TYPE as
+ARRAY, which this function returns.
+
+Important note: the underlying vector is an implementation detail. Even though
+this function exposes it, changes in the implementation may cause this
+function to be removed without further warning."
+ ;; KLUDGE: Without TRULY-THE the system is not smart enough to figure out that
+ ;; the return value is always of the known type.
+ (truly-the (simple-array * (*))
+ (if (array-header-p array)
+ (if (%array-displaced-p array)
+ (error "~S cannot be used with displaced arrays. Use ~S instead."
+ 'array-storage-vector 'array-displacement)
+ (%array-data-vector array))
+ array)))
\f
;;;; used by SORT
projects / sbcl.git / blobdiff