From owner-svn-src-head@freebsd.org Wed Dec 4 03:36:54 2019 Return-Path: Delivered-To: svn-src-head@mailman.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.nyi.freebsd.org (Postfix) with ESMTP id E93801C7AB1; Wed, 4 Dec 2019 03:36:54 +0000 (UTC) (envelope-from dougm@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) server-signature RSA-PSS (4096 bits) client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "Let's Encrypt Authority X3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 47SPfZ5tLyz4KZ2; Wed, 4 Dec 2019 03:36:54 +0000 (UTC) (envelope-from dougm@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id AD5E32206B; Wed, 4 Dec 2019 03:36:54 +0000 (UTC) (envelope-from dougm@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id xB43asvq077058; Wed, 4 Dec 2019 03:36:54 GMT (envelope-from dougm@FreeBSD.org) Received: (from dougm@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id xB43asGj077057; Wed, 4 Dec 2019 03:36:54 GMT (envelope-from dougm@FreeBSD.org) Message-Id: <201912040336.xB43asGj077057@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: dougm set sender to dougm@FreeBSD.org using -f From: Doug Moore Date: Wed, 4 Dec 2019 03:36:54 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r355377 - head/sys/sys X-SVN-Group: head X-SVN-Commit-Author: dougm X-SVN-Commit-Paths: head/sys/sys X-SVN-Commit-Revision: 355377 X-SVN-Commit-Repository: base MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-head@freebsd.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: SVN commit messages for the src tree for head/-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 04 Dec 2019 03:36:55 -0000 Author: dougm Date: Wed Dec 4 03:36:54 2019 New Revision: 355377 URL: https://svnweb.freebsd.org/changeset/base/355377 Log: Change the implementation of bit_ffc_area_at so that, in the worst case, the number of operations spent on each b-bit word is proportional to lg b rather than b. For one word, shrink all regions of 0-bits by size-1 bit positions in no more than O(lg(min(b,size))) operations. In what remains, the first 0-bit is either the start of an area of sufficient size contained within the original word, or the start of an area that could spill over into the next word, and prove to be of sufficient size once the start of that word is examined. Change bit_ffs_area_at similarly. Reviewed by: erj, jacob.e.keller_intel.com MFC with: r354977 Differential Revision: https://reviews.freebsd.org/D22523 Modified: head/sys/sys/bitstring.h Modified: head/sys/sys/bitstring.h ============================================================================== --- head/sys/sys/bitstring.h Wed Dec 4 02:59:50 2019 (r355376) +++ head/sys/sys/bitstring.h Wed Dec 4 03:36:54 2019 (r355377) @@ -277,66 +277,96 @@ bit_ffc(bitstr_t *_bitstr, int _nbits, int *_result) /* Find contiguous sequence of at least size set bits at or after start */ static inline void -bit_ffs_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size, int *_result) +bit_ffs_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size, + int *_result) { - int _index, _end, _i; -again: - /* Find the first set bit */ - bit_ffs_at(_bitstr, _start, _nbits, &_index); - if (_index < 0) { - *_result = -1; - return; - } + bitstr_t *_curbitstr; + bitstr_t _test; + int _value, _offset, _logsize, _b; - /* Make sure there is enough room left in the bitstr */ - _end = _index + _size; - if (_end > _nbits) { + if (_start + _size > _nbits || _nbits <= 0) { *_result = -1; return; } - /* Find the next cleared bit starting at _index, stopping at _end */ - bit_ffc_at(_bitstr, _index, _end, &_i); - if (_i >= 0) { - /* we found a clear bit between _index and _end, so skip ahead - * to the next bit and try again - */ - _start = _i + 1; - goto again; + _logsize = fls(_size - 1); + _value = _start; + _curbitstr = _bitstr + _bit_idx(_start); + _test = ~*_curbitstr; + if (_bit_offset(_start) != 0) + _test |= _bit_make_mask(0, _start - 1); + for (_offset = 0;; _offset -= _BITSTR_BITS, _test = ~*++_curbitstr) { + if (_test != 0) { + /* If leading 0s in _test can finish 0-area, stop. */ + if (_offset + _size < (int)_BITSTR_BITS && + (_test & _bit_make_mask(0, _offset + _size)) == 0) + break; + /* Shrink-left every 0-area in _test by size-1 bits. */ + _b = _logsize; + while ((_test & (_test + 1)) != 0 && _b-- > 0) + _test |= _test >> (((_size - 1) >> _b) + 1) / 2; + /* Find the start of the first 0-area in _test. */ + _offset = (~_test == 0) ? _BITSTR_BITS : + ffsl(~_test) - 1; + _value = (_curbitstr - _bitstr) * _BITSTR_BITS + + _offset; + /* If there's insufficient space left, give up. */ + if (_value + _size > _nbits) { + _value = -1; + break; + } + } + if (_offset + _size <= (int)_BITSTR_BITS) + break; } - *_result = _index; + *_result = _value; } /* Find contiguous sequence of at least size cleared bits at or after start */ static inline void -bit_ffc_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size, int *_result) +bit_ffc_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size, + int *_result) { - int _index, _end, _i; -again: - /* Find the first zero bit */ - bit_ffc_at(_bitstr, _start, _nbits, &_index); - if (_index < 0) { - *_result = -1; - return; - } + bitstr_t *_curbitstr; + bitstr_t _test; + int _value, _offset, _logsize, _b; - /* Make sure there is enough room left in the bitstr */ - _end = _index + _size; - if (_end > _nbits) { + if (_start + _size > _nbits || _nbits <= 0) { *_result = -1; return; } - /* Find the next set bit starting at _index, stopping at _end */ - bit_ffs_at(_bitstr, _index, _end, &_i); - if (_i >= 0) { - /* we found a set bit between _index and _end, so skip ahead - * to the next bit and try again - */ - _start = _i + 1; - goto again; + _logsize = fls(_size - 1); + _value = _start; + _curbitstr = _bitstr + _bit_idx(_start); + _test = *_curbitstr; + if (_bit_offset(_start) != 0) + _test |= _bit_make_mask(0, _start - 1); + for (_offset = 0;; _offset -= _BITSTR_BITS, _test = *++_curbitstr) { + if (_test != 0) { + /* If leading 0s in _test can finish 0-area, stop. */ + if (_offset + _size < (int)_BITSTR_BITS && + (_test & _bit_make_mask(0, _offset + _size)) == 0) + break; + /* Shrink-left every 0-area in _test by size-1 bits. */ + _b = _logsize; + while ((_test & (_test + 1)) != 0 && _b-- > 0) + _test |= _test >> (((_size - 1) >> _b) + 1) / 2; + /* Find the start of the first 0-area in _test. */ + _offset = (~_test == 0) ? _BITSTR_BITS : + ffsl(~_test) - 1; + _value = (_curbitstr - _bitstr) * _BITSTR_BITS + + _offset; + /* If there's insufficient space left, give up. */ + if (_value + _size > _nbits) { + _value = -1; + break; + } + } + if (_offset + _size <= (int)_BITSTR_BITS) + break; } - *_result = _index; + *_result = _value; } /* Find contiguous sequence of at least size set bits in bit string */