libitm/method-wbetl.cc

   1 /* Copyright (C) 2009, 2011 Free Software Foundation, Inc.
   2    Contributed by Richard Henderson <rth@redhat.com>.
   3
   4    This file is part of the GNU Transactional Memory Library (libitm).
   5
   6    Libitm is free software; you can redistribute it and/or modify it
   7    under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 3 of the License, or
   9    (at your option) any later version.
  10
  11    Libitm is distributed in the hope that it will be useful, but WITHOUT ANY
  12    WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  13    FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
  14    more details.
  15
  16    Under Section 7 of GPL version 3, you are granted additional
  17    permissions described in the GCC Runtime Library Exception, version
  18    3.1, as published by the Free Software Foundation.
  19
  20    You should have received a copy of the GNU General Public License and
  21    a copy of the GCC Runtime Library Exception along with this program;
  22    see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23    <http://www.gnu.org/licenses/>.  */
  24
  25 #include "libitm_i.h"
  26
  27 namespace {
  28
  29 using namespace GTM;
  30
  31 class wbetl_dispatch : public abi_dispatch
  32 {
  33  private:
  34   static const size_t RW_SET_SIZE = 4096;
  35
  36   struct r_entry
  37   {
  38     gtm_version version;
  39     gtm_stmlock *lock;
  40   };
  41
  42   r_entry *m_rset_entries;
  43   size_t m_rset_nb_entries;
  44   size_t m_rset_size;
  45
  46   struct w_entry
  47   {
  48     /* There's a hashtable where the locks are held, so multiple
  49        cachelines can hash to a given bucket.  This link points to the
  50        possible next cacheline that also hashes to this bucket.  */
  51     struct w_entry *next;
  52
  53     /* Every entry in this bucket (accessed by NEXT) has the same LOCK
  54        address below.  */
  55     gtm_stmlock *lock;
  56
  57     gtm_cacheline *addr;
  58     gtm_cacheline *value;
  59     gtm_version version;
  60   };
  61
  62   w_entry *m_wset_entries;
  63   size_t m_wset_nb_entries;
  64   size_t m_wset_size;
  65   bool m_wset_reallocate;
  66
  67   gtm_version m_start;
  68   gtm_version m_end;
  69
  70   gtm_cacheline_page *m_cache_page;
  71   unsigned m_n_cache_page;
  72
  73  private:
  74   bool local_w_entry_p (w_entry *w);
  75   bool has_read (gtm_stmlock *lock);
  76   bool validate();
  77   bool extend();
  78
  79   gtm_cacheline *do_write_lock(gtm_cacheline *);
  80   gtm_cacheline *do_after_write_lock(gtm_cacheline *);
  81   const gtm_cacheline *do_read_lock(const gtm_cacheline *, bool);
  82
  83  public:
  84   wbetl_dispatch();
  85
  86   virtual const gtm_cacheline *read_lock(const gtm_cacheline *, ls_modifier);
  87   virtual mask_pair write_lock(gtm_cacheline *, ls_modifier);
  88
  89   virtual bool trycommit();
  90   virtual void rollback();
  91   virtual void reinit();
  92   virtual void fini();
  93   virtual bool trydropreference (void *, size_t);
  94 };
  95
  96 /* Check if W is one of our write locks.  */
  97
  98 inline bool
  99 wbetl_dispatch::local_w_entry_p (w_entry *w)
 100 {
 101   return (m_wset_entries <= w && w < m_wset_entries + m_wset_nb_entries);
 102 }
 103
 104 /* Check if stripe has been read previously.  */
 105
 106 inline bool
 107 wbetl_dispatch::has_read (gtm_stmlock *lock)
 108 {
 109   // ??? Consider using an AA tree to lookup the r_set entries.
 110   size_t n = m_rset_nb_entries;
 111   for (size_t i = 0; i < n; ++i)
 112     if (m_rset_entries[i].lock == lock)
 113       return true;
 114
 115   return false;
 116 }
 117
 118 /* Validate read set, i.e. check if all read addresses are still valid now.  */
 119
 120 bool
 121 wbetl_dispatch::validate ()
 122 {
 123   __sync_synchronize ();
 124
 125   size_t n = m_rset_nb_entries;
 126   for (size_t i = 0; i < n; ++i)
 127     {
 128       r_entry *r = &m_rset_entries[i];
 129       gtm_stmlock l = *r->lock;
 130
 131       if (gtm_stmlock_owned_p (l))
 132         {
 133           w_entry *w = (w_entry *) gtm_stmlock_get_addr (l);
 134
 135           // If someone has locked us, it better be by someone in the
 136           // current thread.
 137           if (!local_w_entry_p (w))
 138             return false;
 139         }
 140       else if (gtm_stmlock_get_version (l) != r->version)
 141         return false;
 142     }
 143
 144   return true;
 145 }
 146
 147 /* Extend the snapshot range.  */
 148
 149 bool
 150 wbetl_dispatch::extend ()
 151 {
 152   gtm_version now = gtm_get_clock ();
 153
 154   if (validate ())
 155     {
 156       m_end = now;
 157       return true;
 158     }
 159   return false;
 160 }
 161
 162 /* Acquire a write lock on ADDR.  */
 163
 164 gtm_cacheline *
 165 wbetl_dispatch::do_write_lock(gtm_cacheline *addr)
 166 {
 167   gtm_stmlock *lock;
 168   gtm_stmlock l, l2;
 169   gtm_version version;
 170   w_entry *w, *prev = NULL;
 171
 172   lock = gtm_get_stmlock (addr);
 173   l = *lock;
 174
 175  restart_no_load:
 176   if (gtm_stmlock_owned_p (l))
 177     {
 178       w = (w_entry *) gtm_stmlock_get_addr (l);
 179
 180       /* Did we previously write the same address?  */
 181       if (local_w_entry_p (w))
 182         {
 183           prev = w;
 184           while (1)
 185             {
 186               if (addr == prev->addr)
 187                 return prev->value;
 188               if (prev->next == NULL)
 189                 break;
 190               prev = prev->next;
 191             }
 192
 193           /* Get version from previous entry write set.  */
 194           version = prev->version;
 195
 196           /* If there's not enough entries, we must reallocate the array,
 197              which invalidates all pointers to write set entries, which
 198              means we have to restart the transaction.  */
 199           if (m_wset_nb_entries == m_wset_size)
 200             {
 201               m_wset_size *= 2;
 202               m_wset_reallocate = true;
 203               gtm_tx()->restart (RESTART_REALLOCATE);
 204             }
 205
 206           w = &m_wset_entries[m_wset_nb_entries];
 207           goto do_write;
 208         }
 209
 210       gtm_tx()->restart (RESTART_LOCKED_WRITE);
 211     }
 212   else
 213     {
 214       version = gtm_stmlock_get_version (l);
 215
 216       /* We might have read an older version previously.  */
 217       if (version > m_end)
 218         {
 219           if (has_read (lock))
 220             gtm_tx()->restart (RESTART_VALIDATE_WRITE);
 221         }
 222
 223       /* Extend write set, aborting to reallocate write set entries.  */
 224       if (m_wset_nb_entries == m_wset_size)
 225         {
 226           m_wset_size *= 2;
 227           m_wset_reallocate = true;
 228           gtm_tx()->restart (RESTART_REALLOCATE);
 229         }
 230
 231       /* Acquire the lock.  */
 232       w = &m_wset_entries[m_wset_nb_entries];
 233       l2 = gtm_stmlock_set_owned (w);
 234       l = __sync_val_compare_and_swap (lock, l, l2);
 235       if (l != l2)
 236         goto restart_no_load;
 237     }
 238
 239  do_write:
 240   m_wset_nb_entries++;
 241   if (prev != NULL)
 242     prev->next = w;
 243   w->next = 0;
 244   w->lock = lock;
 245   w->addr = addr;
 246   w->version = version;
 247
 248   gtm_cacheline_page *page = m_cache_page;
 249   unsigned index = m_n_cache_page;
 250
 251   if (page == NULL || index == gtm_cacheline_page::LINES)
 252     {
 253       gtm_cacheline_page *npage = new gtm_cacheline_page;
 254       npage->prev = page;
 255       m_cache_page = page = npage;
 256       m_n_cache_page = 1;
 257       index = 0;
 258     }
 259   else
 260     m_n_cache_page = index + 1;
 261
 262   gtm_cacheline *line = &page->lines[index];
 263   w->value = line;
 264   page->masks[index] = 0;
 265   *line = *addr;
 266
 267   return line;
 268 }
 269
 270 gtm_cacheline *
 271 wbetl_dispatch::do_after_write_lock (gtm_cacheline *addr)
 272 {
 273   gtm_stmlock *lock;
 274   gtm_stmlock l;
 275   w_entry *w;
 276
 277   lock = gtm_get_stmlock (addr);
 278   l = *lock;
 279   assert (gtm_stmlock_owned_p (l));
 280
 281   w = (w_entry *) gtm_stmlock_get_addr (l);
 282   assert (local_w_entry_p (w));
 283
 284   while (1)
 285     {
 286       if (addr == w->addr)
 287         return w->value;
 288       w = w->next;
 289     }
 290 }
 291
 292 /* Acquire a read lock on ADDR.  */
 293
 294 const gtm_cacheline *
 295 wbetl_dispatch::do_read_lock (const gtm_cacheline *addr, bool after_read)
 296 {
 297   gtm_stmlock *lock;
 298   gtm_stmlock l, l2;
 299   gtm_version version;
 300   w_entry *w;
 301
 302   lock = gtm_get_stmlock (addr);
 303   l = *lock;
 304
 305  restart_no_load:
 306   if (gtm_stmlock_owned_p (l))
 307     {
 308       w = (w_entry *) gtm_stmlock_get_addr (l);
 309
 310       /* Did we previously write the same address?  */
 311       if (local_w_entry_p (w))
 312         {
 313           while (1)
 314             {
 315               if (addr == w->addr)
 316                 return w->value;
 317               if (w->next == NULL)
 318                 return addr;
 319               w = w->next;
 320             }
 321         }
 322
 323       gtm_tx()->restart (RESTART_LOCKED_READ);
 324     }
 325
 326   version = gtm_stmlock_get_version (l);
 327
 328   /* If version is no longer valid, re-validate the read set.  */
 329   if (version > m_end)
 330     {
 331       if (!extend ())
 332         gtm_tx()->restart (RESTART_VALIDATE_READ);
 333
 334       if (!after_read)
 335         {
 336           // Verify that the version has not yet been overwritten.  The read
 337           // value has not yet been added to read set and may not have been
 338           // checked during the extend.
 339           //
 340           // ??? This only makes sense if we're actually reading the value
 341           // and returning it now -- which I believe the original TinySTM
 342           // did.  This doesn't make a whole lot of sense when we're
 343           // manipulating cachelines as we are now.  Do we need some other
 344           // form of lock verification here, or is the validate call in
 345           // trycommit sufficient?
 346
 347           __sync_synchronize ();
 348           l2 = *lock;
 349           if (l != l2)
 350             {
 351               l = l2;
 352               goto restart_no_load;
 353             }
 354         }
 355     }
 356
 357   if (!after_read)
 358     {
 359       r_entry *r;
 360
 361       /* Add the address and version to the read set.  */
 362       if (m_rset_nb_entries == m_rset_size)
 363         {
 364           m_rset_size *= 2;
 365
 366           m_rset_entries = (r_entry *)
 367             xrealloc (m_rset_entries, m_rset_size * sizeof(r_entry));
 368         }
 369       r = &m_rset_entries[m_rset_nb_entries++];
 370       r->version = version;
 371       r->lock = lock;
 372     }
 373
 374   return addr;
 375 }
 376
 377 const gtm_cacheline *
 378 wbetl_dispatch::read_lock (const gtm_cacheline *addr, ls_modifier ltype)
 379 {
 380   switch (ltype)
 381     {
 382     case NONTXNAL:
 383       return addr;
 384     case R:
 385       return do_read_lock (addr, false);
 386     case RaR:
 387       return do_read_lock (addr, true);
 388     case RaW:
 389       return do_after_write_lock (const_cast<gtm_cacheline *>(addr));
 390     case RfW:
 391       return do_write_lock (const_cast<gtm_cacheline *>(addr));
 392     default:
 393       abort ();
 394     }
 395 }
 396
 397 abi_dispatch::mask_pair
 398 wbetl_dispatch::write_lock (gtm_cacheline *addr, ls_modifier ltype)
 399 {
 400   gtm_cacheline *line;
 401
 402   switch (ltype)
 403     {
 404     case NONTXNAL:
 405       return mask_pair (addr, &mask_sink);
 406     case W:
 407     case WaR:
 408       line = do_write_lock (addr);
 409       break;
 410     case WaW:
 411       line = do_after_write_lock (addr);
 412       break;
 413     default:
 414       abort ();
 415     }
 416
 417   return mask_pair (line, gtm_cacheline_page::mask_for_page_line (line));
 418 }
 419
 420 /* Commit the transaction.  */
 421
 422 bool
 423 wbetl_dispatch::trycommit ()
 424 {
 425   const size_t n = m_wset_nb_entries;
 426   if (n != 0)
 427     {
 428       /* Get commit timestamp.  */
 429       gtm_version t = gtm_inc_clock ();
 430
 431       /* Validate only if a concurrent transaction has started since.  */
 432       if (m_start != t - 1 && !validate ())
 433         return false;
 434
 435       /* Install new versions.  */
 436       for (size_t i = 0; i < n; ++i)
 437         {
 438           w_entry *w = &m_wset_entries[i];
 439           gtm_cacheline_mask mask
 440             = *gtm_cacheline_page::mask_for_page_line (w->value);
 441
 442           /* Filter out any updates that overlap the libitm stack.  */
 443           mask = gtm_mask_stack (w->addr, mask);
 444
 445           gtm_cacheline::copy_mask (w->addr, w->value, mask);
 446         }
 447
 448       /* Only emit barrier after all cachelines are copied.  */
 449       gtm_cacheline::copy_mask_wb ();
 450
 451       /* Drop locks.  */
 452       for (size_t i = 0; i < n; ++i)
 453         {
 454           w_entry *w = &m_wset_entries[i];
 455
 456           /* Every link along the chain has the same lock, but only
 457              bother dropping the lock once per bucket (at the end).  */
 458           if (w->next == NULL)
 459             *w->lock = gtm_stmlock_set_version (t);
 460         }
 461     }
 462
 463   __sync_synchronize ();
 464   return true;
 465 }
 466
 467 void
 468 wbetl_dispatch::rollback ()
 469 {
 470   /* Drop locks.  */
 471   const size_t n = m_wset_nb_entries;
 472   for (size_t i = 0; i < n; ++i)
 473     {
 474       w_entry *w = &m_wset_entries[i];
 475
 476       /* Every link along the chain has the same lock, but only
 477          bother dropping the lock once per bucket (at the end).  */
 478       if (w->next == NULL)
 479         *w->lock = gtm_stmlock_set_version (w->version);
 480     }
 481
 482   __sync_synchronize ();
 483 }
 484
 485 void
 486 wbetl_dispatch::reinit ()
 487 {
 488   gtm_cacheline_page *page;
 489
 490   m_rset_nb_entries = 0;
 491   m_wset_nb_entries = 0;
 492
 493   if (m_wset_reallocate)
 494     {
 495       m_wset_reallocate = 0;
 496       m_wset_entries = (w_entry *)
 497         xrealloc (m_wset_entries, m_wset_size * sizeof(w_entry));
 498     }
 499
 500   page = m_cache_page;
 501   if (page)
 502     {
 503       /* Release all but one of the pages of cachelines.  */
 504       gtm_cacheline_page *prev = page->prev;
 505       if (prev)
 506         {
 507           page->prev = 0;
 508           delete prev;
 509         }
 510
 511       /* Start the next cacheline allocation from the beginning.  */
 512       m_n_cache_page = 0;
 513     }
 514
 515   m_start = m_end = gtm_get_clock ();
 516 }
 517
 518 void
 519 wbetl_dispatch::fini ()
 520 {
 521   delete m_cache_page;
 522   free (m_rset_entries);
 523   free (m_wset_entries);
 524   delete this;
 525 }
 526
 527 /* Attempt to drop any internal references to PTR.  Return TRUE if successful.
 528
 529    This is an adaptation of the transactional memcpy function.
 530
 531    What we do here is flush out the current transactional content of
 532    PTR to real memory, and remove the write mask bits associated with
 533    it so future commits will ignore this piece of memory.  */
 534
 535 bool
 536 wbetl_dispatch::trydropreference (void *ptr, size_t size)
 537 {
 538   if (size == 0)
 539     return true;
 540
 541   if (!validate ())
 542     return false;
 543
 544   uintptr_t isrc = (uintptr_t)ptr;
 545   // The position in the source cacheline where *PTR starts.
 546   uintptr_t sofs = isrc & (CACHELINE_SIZE - 1);
 547   gtm_cacheline *src
 548     = reinterpret_cast<gtm_cacheline *>(isrc & -CACHELINE_SIZE);
 549   unsigned char *dst = (unsigned char *)ptr;
 550   abi_dispatch::mask_pair pair;
 551
 552   // If we're trying to drop a reference, we should already have a
 553   // write lock on it.  If we don't have one, there's no work to do.
 554   if (!gtm_stmlock_owned_p (*gtm_get_stmlock (src)))
 555     return true;
 556
 557   // We copy the data in three stages:
 558
 559   // (a) Copy stray bytes at the beginning that are smaller than a
 560   // cacheline.
 561   if (sofs != 0)
 562     {
 563       size_t sleft = CACHELINE_SIZE - sofs;
 564       size_t min = (size <= sleft ? size : sleft);
 565
 566       // WaW will give us the current locked entry.
 567       pair = this->write_lock (src, WaW);
 568
 569       // *jedi mind wave*...these aren't the droids you're looking for.
 570       *pair.mask &= ~((((gtm_cacheline_mask)1 << min) - 1) << sofs);
 571
 572       memcpy (dst, &pair.line->b[sofs], min);
 573       dst += min;
 574       src++;
 575       size -= min;
 576     }
 577
 578   // (b) Copy subsequent cacheline sized chunks.
 579   while (size >= CACHELINE_SIZE)
 580     {
 581       pair = this->write_lock(src, WaW);
 582       *pair.mask = 0;
 583       memcpy (dst, pair.line, CACHELINE_SIZE);
 584       dst += CACHELINE_SIZE;
 585       src++;
 586       size -= CACHELINE_SIZE;
 587     }
 588
 589   // (c) Copy anything left over.
 590   if (size != 0)
 591     {
 592       pair = this->write_lock(src, WaW);
 593       *pair.mask &= ~(((gtm_cacheline_mask)1 << size) - 1);
 594       memcpy (dst, pair.line, size);
 595     }
 596
 597   // No need to drop locks, since we're going to abort the transaction
 598   // anyhow.
 599
 600   return true;
 601 }
 602
 603
 604 wbetl_dispatch::wbetl_dispatch ()
 605   : abi_dispatch (false, false)
 606 {
 607   m_rset_entries = (r_entry *) xmalloc (RW_SET_SIZE * sizeof(r_entry));
 608   m_rset_nb_entries = 0;
 609   m_rset_size = RW_SET_SIZE;
 610
 611   m_wset_entries = (w_entry *) xmalloc (RW_SET_SIZE * sizeof(w_entry));
 612   m_wset_nb_entries = 0;
 613   m_wset_size = RW_SET_SIZE;
 614   m_wset_reallocate = false;
 615
 616   m_start = m_end = gtm_get_clock ();
 617
 618   m_cache_page = 0;
 619   m_n_cache_page = 0;
 620 }
 621
 622 } // anon namespace
 623
 624 abi_dispatch *
 625 GTM::dispatch_wbetl ()
 626 {
 627   return new wbetl_dispatch ();
 628 }