RFR: 8213415: BitMap::word_index_round_up overflow problems

[Stefan Karlsson]

Hi Thomas,

On 2019-12-03 09:28, Thomas Stüfe wrote:
> Hi Stefan,
> 
> On Mon, Dec 2, 2019 at 11:11 AM Stefan Karlsson 
> <stefan.karlsson at oracle.com <mailto:stefan.karlsson at oracle.com>> wrote:
> 
>     On 2019-11-29 21:37, Kim Barrett wrote:
>      >> On Nov 29, 2019, at 3:03 AM, Thomas Stüfe
>     <thomas.stuefe at gmail.com <mailto:thomas.stuefe at gmail.com>> wrote:
>      >>
>      >> Side note, I was interested in using smaller types because long
>     term I would like to have a BitMap class in cases where I today use
>     little hand written bitmaps. As it is now, BitMap has a pointer and
>     a size, which makes it a 16byte structure on 64 bit, which is rather
>     fat. The indirection is also often unwanted. I would like to have a
>     BitMap class which contains directly the data as member(s), e.g. one
>     where it just has a 16bit word or, maybe, an array of multiple
>     words. That would make this structure a lot smaller and better
>     suited to be included in space sensitive structures.
>      > There was some discussion here in Oracle about this sort of thing a
>      > while ago. Looking back over that discussion, I don't think we got
>      > very far with a statically sized bitmap, just some handwaving. I
>     think
>      > the interest is there, but ideas (and time to persue them!) are
>      > needed.
> 
>     FWIW, see the usage of BitMapView in zLiveMap.hpp and
>     zLiveMap.inline.hpp.
> 
>     The bitmap backing is a single word inside ZLiveMap:
>         BitMap::bm_word_t _segment_live_bits;
> 
>     and the size is constant:
>         static const size_t nsegments = 64;
> 
>     The views are created with:
>     inline BitMapView ZLiveMap::segment_live_bits() {
>         return BitMapView(&_segment_live_bits, nsegments);
>     }
> 
>     and then used with:
>     inline bool ZLiveMap::is_segment_live(BitMap::idx_t segment) const {
>         return segment_live_bits().par_at(segment);
>     }
> 
>     All this gets inlined as expected.
> 
>     It doesn't support sizes less than a word, but it does support
>     arrays of
>     multiple words.
> 
>     StefanK
> 
> 
> I was aware that we could put the Bitmap over existing memory, but it 
> did not occur to me to do this just temporarily for one operation... So, 
> all that business above (Bitmap construction, copying etc) gets 
> optimized away to a simple load and an or?

There are some extra masking and shifting as well. Some of that could 
probably be optimized away with a special-built bitmap.

If we take this function as an example:

void ZLiveMap::reset_segment(BitMap::idx_t segment) {
   bool contention = false;

   if (!claim_segment(segment)) {

with claim_segment:
inline bool ZLiveMap::claim_segment(BitMap::idx_t segment) {
   return segment_claim_bits().par_set_bit(segment, memory_order_acq_rel);
}

and par_set_bit:
inline bool BitMap::par_set_bit(idx_t bit, atomic_memory_order 
memory_order) {
   verify_index(bit);
   volatile bm_word_t* const addr = word_addr(bit);
   const bm_word_t mask = bit_mask(bit);

and we correlate that with the generated code:

0000000000e00910 <_ZN8ZLiveMap13reset_segmentEm>:
   e00910:	55                   	push   %rbp
   e00911:	48 89 f1             	mov    %rsi,%rcx  // segment
   e00914:	83 e1 3f             	and    $0x3f,%ecx // bit_in_word
   e00917:	48 89 e5             	mov    %rsp,%rbp
   e0091a:	41 57                	push   %r15
   e0091c:	41 56                	push   %r14
   e0091e:	49 89 f6             	mov    %rsi,%r14
   e00921:	41 55                	push   %r13
   e00923:	49 c1 ee 06          	shr    $0x6,%r14 // word_index
   e00927:	49 89 fd             	mov    %rdi,%r13
   e0092a:	41 54                	push   %r12
   e0092c:	49 c1 e6 03          	shl    $0x3,%r14
   e00930:	49 89 f4             	mov    %rsi,%r12
   e00933:	53                   	push   %rbx
   e00934:	4a 8d 7c 37 18       	lea    0x18(%rdi,%r14,1),%rdi // word_addr
   e00939:	bb 01 00 00 00       	mov    $0x1,%ebx
   e0093e:	48 d3 e3             	shl    %cl,%rbx // bit_mask
   e00941:	48 83 ec 08          	sub    $0x8,%rsp
   e00945:	48 8b 0f             	mov    (%rdi),%rcx // load
   e00948:	eb 16                	jmp    e00960 
<_ZN8ZLiveMap13reset_segmentEm+0x50>
   e0094a:	66 0f 1f 44 00 00    	nopw   0x0(%rax,%rax,1)
   e00950:	48 89 c8             	mov    %rcx,%rax
   e00953:	f0 48 0f b1 17       	lock cmpxchg %rdx,(%rdi)
   e00958:	48 39 c1             	cmp    %rax,%rcx
   e0095b:	74 43                	je     e009a0 
<_ZN8ZLiveMap13reset_segmentEm+0x90>

There's no traces of the temporary bitmap view, as far as I can see.

StefanK

> 
> Thanks, Thomas
> 
>