[libomptarget] Avoid deleting the same entry multiple times

[ye-luo]

Summary

Once refcount drops to 0, remove the entry from the HDTTMap but delay the deletion of the actual entry.

[jdoerfert]

I thought about this but IIRC, this doesn't work either. Now you have no way to prevent races between the copy back and copy to since the entry is gone while the copy back runs.

[ye-luo]

In D132532#3745640, @jdoerfert wrote:

I thought about this but IIRC, this doesn't work either. Now you have no way to prevent races between the copy back and copy to since the entry is gone while the copy back runs.

I thought about the racing. If race to write the same data, there is no harm. If race to write different data, the source of race is user program which needs to protect the race anyway.

[gValarini]

In D132532#3745645, @ye-luo wrote:

In D132532#3745640, @jdoerfert wrote:

I thought about this but IIRC, this doesn't work either. Now you have no way to prevent races between the copy back and copy to since the entry is gone while the copy back runs.

I thought about the racing. If race to write the same data, there is no harm. If race to write different data, the source of race is user program which needs to protect the race anyway.

I believe what @jdoerfert is trying to say is that the race will happen between a thread deleting the device data and another making the data transfer. Imagine the following case:

• Thread A: is not the "owner" (IsOwned == false) of the entry but will do a data transfer.
• Thread B: is the "owner" (IsOwned == true) of the entry and will delete it.

If A is switched out of execution right after getTgtPtrBegin returns, B might remove the data before A starts any data transfer. This will lead to a segfault on the device side. Although it seems to be a problem with the user program, I think it should lead to data corruption and not a segfault. I also believe this may happen on correct programs, but I cannot think of a simple example right now.

I was planning to send a patch with this same fix this week. It was quite similar to this one, but it also had a new reference counter designed to track threads using the entry on the data end function. This way, multiple threads might get the entry, but only the last one would delete the buffer and the entry data.

[jdoerfert]

In D132532#3745645, @ye-luo wrote:

In D132532#3745640, @jdoerfert wrote:

I thought about this but IIRC, this doesn't work either. Now you have no way to prevent races between the copy back and copy to since the entry is gone while the copy back runs.

I thought about the racing. If race to write the same data, there is no harm. If race to write different data, the source of race is user program which needs to protect the race anyway.

I still believe there is a problem.

T1: copy back old device memory into HostMem after entry has been deleted
T2: copy from HostMem into some new device region as the entry is new

We cannot use events or anything to prevent this race on the host memory and since maps should be atomic we break the program.

Where am I wrong?

[ye-luo]

In D132532#3745744, @gValarini wrote:

In D132532#3745645, @ye-luo wrote:

In D132532#3745640, @jdoerfert wrote:

I thought about this but IIRC, this doesn't work either. Now you have no way to prevent races between the copy back and copy to since the entry is gone while the copy back runs.

I thought about the racing. If race to write the same data, there is no harm. If race to write different data, the source of race is user program which needs to protect the race anyway.

I believe what @jdoerfert is trying to say is that the race will happen between a thread deleting the device data and another making the data transfer. Imagine the following case:

• Thread A: is not the "owner" (IsOwned == false) of the entry but will do a data transfer.
• Thread B: is the "owner" (IsOwned == true) of the entry and will delete it.

If A is switched out of execution right after getTgtPtrBegin returns, B might remove the data before A starts any data transfer. This will lead to a segfault on the device side. Although it seems to be a problem with the user program, I think it should lead to data corruption and not a segfault. I also believe this may happen on correct programs, but I cannot think of a simple example right now.

I was planning to send a patch with this same fix this week. It was quite similar to this one, but it also had a new reference counter designed to track threads using the entry on the data end function. This way, multiple threads might get the entry, but only the last one would delete the buffer and the entry data.

Your example is valid. I think we probably need to distinguish the transfer not caused by refcount to 0 and transfer caused by refcount to 0.
transfer not caused by refcount to 0 needs to be placed before actually adjusting the recount. I feel we need probably write down a few rules before devising a scheme.
Another more conservative route I though about is only schedule ahead transfers of refcount=INF.

tracking threads. My quick take will be another can of worms. I need to think about it when your patch shows up.

[ye-luo]

In D132532#3745747, @jdoerfert wrote:

In D132532#3745645, @ye-luo wrote:

In D132532#3745640, @jdoerfert wrote:

I thought about this but IIRC, this doesn't work either. Now you have no way to prevent races between the copy back and copy to since the entry is gone while the copy back runs.

I thought about the racing. If race to write the same data, there is no harm. If race to write different data, the source of race is user program which needs to protect the race anyway.

I still believe there is a problem.

T1: copy back old device memory into HostMem after entry has been deleted
T2: copy from HostMem into some new device region as the entry is new

We cannot use events or anything to prevent this race on the host memory and since maps should be atomic we break the program.

Where am I wrong?

You are right. There is potential data corruption. The H2D to a new device memory location may start before D2H completes.

[gValarini]

In D132532#3745885, @ye-luo wrote:

tracking threads. My quick take will be another can of worms. I need to think about it when your patch shows up.

I have just submitted patch D132676 with the implementation that I described before. I believe that by tracking the threads in a scoped manner, we may reduce the work of maintaining the solution. What do you think?

openmp/libomptarget/include/device.h

 //===----------- device.h - Target independent OpenMP target RTL ----------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
private:
   static const uint64_t INFRefCount = ~(uint64_t)0;
   static std::string refCountToStr(uint64_t RefCount) {
     return RefCount == INFRefCount ? "INF" : std::to_string(RefCount);
   }
 
   struct StatesTy {
     StatesTy(uint64_t DRC, uint64_t HRC)
         : DynRefCount(DRC), HoldRefCount(HRC),
-          MayContainAttachedPointers(false), DeleteThreadId(std::thread::id()) {
+          MayContainAttachedPointers(false) {
     }
     /// The dynamic reference count is the standard reference count as of OpenMP
     /// 4.5.  The hold reference count is an OpenMP extension for the sake of
     /// OpenACC support.
     ///
     /// The 'ompx_hold' map type modifier is permitted only on "omp target" and
     /// "omp target data", and "delete" is permitted only on "omp target exit
     /// data" and associated runtime library routines.  As a result, we really
struct StatesTy {
     /// Pointer to the event corresponding to the data update of this map.
     /// Note: At present this event is created when the first data transfer from
     /// host to device is issued, and only being used for H2D. It is not used
     /// for data transfer in another direction (device to host). It is still
     /// unclear whether we need it for D2H. If in the future we need similar
     /// mechanism for D2H, and if the event cannot be shared between them, Event
     /// should be written as <tt>void *Event[2]</tt>.
     void *Event = nullptr;
-
-    /// The id of the thread responsible for deleting this entry. This thread
-    /// set the reference count to zero *last*. Other threads might reuse the
-    /// entry while it is marked for deletion but not yet deleted (e.g., the
-    /// data is still being moved back). If another thread reuses the entry we
-    /// will have a non-zero reference count *or* the thread will have changed
-    /// this id, effectively taking over deletion responsibility.
-    std::thread::id DeleteThreadId;
   };
   // When HostDataToTargetTy is used by std::set, std::set::iterator is const
   // use unique_ptr to make States mutable.
   const std::unique_ptr<StatesTy> States;
 
 public:
   HostDataToTargetTy(uintptr_t BP, uintptr_t B, uintptr_t E, uintptr_t TB,
                      bool UseHoldRefCount, map_var_info_t Name = nullptr,
public:
 
   /// Get the event bound to this data map.
   void *getEvent() const { return States->Event; }
 
   /// Add a new event, if necessary.
   /// Returns OFFLOAD_FAIL if something went wrong, OFFLOAD_SUCCESS otherwise.
   int addEventIfNecessary(DeviceTy &Device, AsyncInfoTy &AsyncInfo) const;
 
-  /// Indicate that the current thread expected to delete this entry.
-  void setDeleteThreadId() const {
-    States->DeleteThreadId = std::this_thread::get_id();
-  }
-
-  /// Return the thread id of the thread expected to delete this entry.
-  std::thread::id getDeleteThreadId() const { return States->DeleteThreadId; }
-
   /// Set the event bound to this data map.
   void setEvent(void *Event) const { States->Event = Event; }
 
   /// Reset the specified reference count unless it's infinity.  Reset to 1
   /// (even if currently 0) so it can be followed by a decrement.
   void resetRefCount(bool UseHoldRefCount) const {
     uint64_t &ThisRefCount =
         UseHoldRefCount ? States->HoldRefCount : States->DynRefCount;

 /// This struct will be returned by \p DeviceTy::getTargetPointer which provides
 /// more data than just a target pointer.
 struct TargetPointerResultTy {
   struct {
     /// If the map table entry is just created
     unsigned IsNewEntry : 1;
     /// If the pointer is actually a host pointer (when unified memory enabled)
     unsigned IsHostPointer : 1;
-  } Flags = {0, 0};
+    unsigned IsOwned : 1;
+  } Flags = {0, 0, 0};
 
   /// The corresponding map table entry which is stable.
   HostDataToTargetTy *Entry = nullptr;
 
   /// The corresponding target pointer
   void *TargetPointer = nullptr;
 };
 
struct DeviceTy {
 
   /// Deallocate \p LR and remove the entry. Assume the total reference count is
   /// zero and the calling thread is the deleting thread for \p LR. \p HDTTMap
   /// ensure the caller holds exclusive access and can modify the map. Return \c
   /// OFFLOAD_SUCCESS if the map entry existed, and return \c OFFLOAD_FAIL if
   /// not. It is the caller's responsibility to skip calling this function if
   /// the map entry is not expected to exist because \p HstPtrBegin uses shared
   /// memory.
-  int deallocTgtPtr(HDTTMapAccessorTy &HDTTMap, LookupResult LR, int64_t Size);
+  int eraseHDTTMapEntry(HDTTMapAccessorTy &HDTTMap, LookupResult LR);
+  int deallocTgtPtr(HostDataToTargetTy *Entry, int64_t Size);
 
   int associatePtr(void *HstPtrBegin, void *TgtPtrBegin, int64_t Size);
   int disassociatePtr(void *HstPtrBegin);
 
   // calls to RTL
   int32_t initOnce();
   __tgt_target_table *loadBinary(void *Img);
 

openmp/libomptarget/src/device.cpp

 //===--------- device.cpp - Target independent OpenMP target RTL ----------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
if (ForceDelete) {
       assert(IsLast == HT.decShouldRemove(UseHoldRefCount) &&
              "expected correct IsLast prediction for reset");
     }
 
     const char *RefCountAction;
     if (!UpdateRefCount) {
       RefCountAction = " (update suppressed)";
     } else if (IsLast) {
-      // Mark the entry as to be deleted by this thread. Another thread might
-      // reuse the entry and take "ownership" for the deletion while this thread
-      // is waiting for data transfers. That is fine and the current thread will
-      // simply skip the deletion step then.
-      HT.setDeleteThreadId();
       HT.decRefCount(UseHoldRefCount);
       assert(HT.getTotalRefCount() == 0 &&
              "Expected zero reference count when deletion is scheduled");
       if (ForceDelete)
         RefCountAction = " (reset, delayed deletion)";
       else
         RefCountAction = " (decremented, delayed deletion)";
     } else {
if (LR.Flags.IsContained ||
     // use directly from the host.
     DP("Get HstPtrBegin " DPxMOD " Size=%" PRId64 " for unified shared "
        "memory\n",
        DPxPTR((uintptr_t)HstPtrBegin), Size);
     IsHostPtr = true;
     TargetPointer = HstPtrBegin;
   }
 
-  return {{IsNew, IsHostPtr}, LR.Entry, TargetPointer};
+  const bool TransferOwnership = IsLast && UpdateRefCount;
+  if (TransferOwnership) 
+    eraseHDTTMapEntry(HDTTMap, LR);
+
+  return {{IsNew, IsHostPtr, TransferOwnership}, LR.Entry, TargetPointer};
 }
 
 // Return the target pointer begin (where the data will be moved).
 void *DeviceTy::getTgtPtrBegin(HDTTMapAccessorTy &HDTTMap, void *HstPtrBegin,
                                int64_t Size) {
   uintptr_t HP = (uintptr_t)HstPtrBegin;
   LookupResult LR = lookupMapping(HDTTMap, HstPtrBegin, Size);
   if (LR.Flags.IsContained || LR.Flags.ExtendsBefore || LR.Flags.ExtendsAfter) {
     auto &HT = *LR.Entry;
     uintptr_t TP = HT.TgtPtrBegin + (HP - HT.HstPtrBegin);
     return (void *)TP;
   }
 
   return NULL;
 }
 
-int DeviceTy::deallocTgtPtr(HDTTMapAccessorTy &HDTTMap, LookupResult LR,
-                            int64_t Size) {
+int DeviceTy::eraseHDTTMapEntry(HDTTMapAccessorTy &HDTTMap, LookupResult LR) {
   // Check if the pointer is contained in any sub-nodes.
   if (!(LR.Flags.IsContained || LR.Flags.ExtendsBefore ||
         LR.Flags.ExtendsAfter)) {
     REPORT("Section to delete (hst addr " DPxMOD ") does not exist in the"
            " allocated memory\n",
            DPxPTR(LR.Entry->HstPtrBegin));
     return OFFLOAD_FAIL;
   }
 
   auto &HT = *LR.Entry;
   // Verify this thread is still in charge of deleting the entry.
   assert(HT.getTotalRefCount() == 0 &&
-         HT.getDeleteThreadId() == std::this_thread::get_id() &&
          "Trying to delete entry that is in use or owned by another thread.");
 
+  HDTTMap->erase(LR.Entry);
+  return OFFLOAD_SUCCESS;
+}
+
+int DeviceTy::deallocTgtPtr(HostDataToTargetTy *Entry, int64_t Size) {
+  auto &HT = *Entry;
   DP("Deleting tgt data " DPxMOD " of size %" PRId64 "\n",
      DPxPTR(HT.TgtPtrBegin), Size);
   deleteData((void *)HT.TgtPtrBegin);
   INFO(OMP_INFOTYPE_MAPPING_CHANGED, DeviceID,
        "Removing map entry with HstPtrBegin=" DPxMOD ", TgtPtrBegin=" DPxMOD
        ", Size=%" PRId64 ", Name=%s\n",
        DPxPTR(HT.HstPtrBegin), DPxPTR(HT.TgtPtrBegin), Size,
        (HT.HstPtrName) ? getNameFromMapping(HT.HstPtrName).c_str() : "unknown");
-  void *Event = LR.Entry->getEvent();
-  HDTTMap->erase(LR.Entry);
-  delete LR.Entry;
+  void *Event = Entry->getEvent();
+  delete Entry;
 
   int Ret = OFFLOAD_SUCCESS;
   if (Event && destroyEvent(Event) != OFFLOAD_SUCCESS) {
     REPORT("Failed to destroy event " DPxMOD "\n", DPxPTR(Event));
     Ret = OFFLOAD_FAIL;
   }
 
   return Ret;

openmp/libomptarget/src/omptarget.cpp

 //===------ omptarget.cpp - Target independent OpenMP target RTL -- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
struct PostProcessingInfo {
   int64_t DataSize;
 
   /// The mapping type (bitfield).
   int64_t ArgType;
 
   /// The target pointer information.
   TargetPointerResultTy TPR;
 
-  /// Are we expecting to delete this entry or not. Even if set, we might not
-  /// delete the entry if another thread reused the entry in the meantime.
-  bool DelEntry;
-
-  PostProcessingInfo(void *HstPtr, int64_t Size, int64_t ArgType, bool DelEntry,
+  PostProcessingInfo(void *HstPtr, int64_t Size, int64_t ArgType,
                      TargetPointerResultTy TPR)
-      : HstPtrBegin(HstPtr), DataSize(Size), ArgType(ArgType), TPR(TPR),
-        DelEntry(DelEntry) {}
+      : HstPtrBegin(HstPtr), DataSize(Size), ArgType(ArgType), TPR(TPR)
+  {}
 };
 
 /// Apply \p CB to the shadow map pointer entries in the range \p Begin, to
 /// \p Begin + \p Size. \p CB is called with a locked shadow pointer map and the
 /// passed iterator can be updated. If the callback returns OFFLOAD_FAIL the
 /// rest of the map is not checked anymore.
 template <typename CBTy>
 static void applyToShadowMapEntries(DeviceTy &Device, CBTy CB, void *Begin,

 
 /// Internal function to undo the mapping and retrieve the data from the device.
 int targetDataEnd(ident_t *Loc, DeviceTy &Device, int32_t ArgNum,
                   void **ArgBases, void **Args, int64_t *ArgSizes,
                   int64_t *ArgTypes, map_var_info_t *ArgNames,
                   void **ArgMappers, AsyncInfoTy &AsyncInfo, bool FromMapper) {
   int Ret;
   SmallVector<PostProcessingInfo> PostProcessingPtrs;
-  void *FromMapperBase = nullptr;
   // process each input.
   for (int32_t I = ArgNum - 1; I >= 0; --I) {
     // Ignore private variables and arrays - there is no mapping for them.
     // Also, ignore the use_device_ptr directive, it has no effect here.
     if ((ArgTypes[I] & OMP_TGT_MAPTYPE_LITERAL) ||
         (ArgTypes[I] & OMP_TGT_MAPTYPE_PRIVATE))
       continue;
 
if ((ArgTypes[I] & OMP_TGT_MAPTYPE_FROM) || DelEntry) {
           // also copy-back a value we would race.
           if (IsLast) {
             if (TPR.Entry->addEventIfNecessary(Device, AsyncInfo) !=
                 OFFLOAD_SUCCESS)
               return OFFLOAD_FAIL;
           }
         }
       }
-      if (DelEntry && FromMapper && I == 0) {
-        DelEntry = false;
-        FromMapperBase = HstPtrBegin;
-      }
 
       // Add pointer to the buffer for post-synchronize processing.
-      PostProcessingPtrs.emplace_back(HstPtrBegin, DataSize, ArgTypes[I],
-                                      DelEntry && !IsHostPtr, TPR);
+      PostProcessingPtrs.emplace_back(HstPtrBegin, DataSize, ArgTypes[I], TPR);
     }
   }
 
   // TODO: We should not synchronize here but pass the AsyncInfo object to the
   //       allocate/deallocate device APIs.
   //
   // We need to synchronize before deallocating data.
   Ret = AsyncInfo.synchronize();
   if (Ret != OFFLOAD_SUCCESS)
     return OFFLOAD_FAIL;
 
   // Deallocate target pointer
   for (PostProcessingInfo &Info : PostProcessingPtrs) {
-    // If we marked the entry to be deleted we need to verify no other thread
-    // reused it by now. If deletion is still supposed to happen by this thread
-    // LR will be set and exclusive access to the HDTT map will avoid another
-    // thread reusing the entry now. Note that we do not request (exclusive)
-    // access to the HDTT map if Info.DelEntry is not set.
-    LookupResult LR;
-    DeviceTy::HDTTMapAccessorTy HDTTMap =
-        Device.HostDataToTargetMap.getExclusiveAccessor(!Info.DelEntry);
-
-    if (Info.DelEntry) {
-      LR = Device.lookupMapping(HDTTMap, Info.HstPtrBegin, Info.DataSize);
-      if (LR.Entry->getTotalRefCount() != 0 ||
-          LR.Entry->getDeleteThreadId() != std::this_thread::get_id()) {
-        // The thread is not in charge of deletion anymore. Give up access to
-        // the HDTT map and unset the deletion flag.
-        HDTTMap.destroy();
-        Info.DelEntry = false;
-      }
-    }
-
+    bool DelEntry = Info.TPR.Flags.IsOwned;
     // If we copied back to the host a struct/array containing pointers, we
     // need to restore the original host pointer values from their shadow
     // copies. If the struct is going to be deallocated, remove any remaining
     // shadow pointer entries for this struct.
     auto CB = [&](ShadowPtrListTy::iterator &Itr) {
       // If we copied the struct to the host, we need to restore the pointer.
       if (Info.ArgType & OMP_TGT_MAPTYPE_FROM) {
         void **ShadowHstPtrAddr = (void **)Itr->first;
         *ShadowHstPtrAddr = Itr->second.HstPtrVal;
         DP("Restoring original host pointer value " DPxMOD " for host "
            "pointer " DPxMOD "\n",
            DPxPTR(Itr->second.HstPtrVal), DPxPTR(ShadowHstPtrAddr));
       }
       // If the struct is to be deallocated, remove the shadow entry.
-      if (Info.DelEntry) {
+      if (DelEntry) {
         DP("Removing shadow pointer " DPxMOD "\n", DPxPTR((void **)Itr->first));
         auto OldItr = Itr;
         Itr++;
         Device.ShadowPtrMap.erase(OldItr);
       } else {
         ++Itr;
       }
       return OFFLOAD_SUCCESS;
     };
     applyToShadowMapEntries(Device, CB, Info.HstPtrBegin, Info.DataSize,
                             Info.TPR);
 
     // If we are deleting the entry the DataMapMtx is locked and we own the
     // entry.
-    if (Info.DelEntry) {
-      if (!FromMapperBase || FromMapperBase != Info.HstPtrBegin)
-        Ret = Device.deallocTgtPtr(HDTTMap, LR, Info.DataSize);
+    if (DelEntry) {
+      Ret = Device.deallocTgtPtr(Info.TPR.Entry, Info.DataSize);
 
       if (Ret != OFFLOAD_SUCCESS) {
         REPORT("Deallocating data from device failed.\n");
         break;
       }
     }
   }