[PGO] Remove data races on Data->Values field

[davidxl]

Summary

The Values field of the per-function data structure is overloaded for two different purposes. At runtime time, the field points to the in-memory value profile data, but when the data is serialized to disk, its value will be changed to point to internals of value profile data's serialization buffer (continuous) -- which are later relocated during profile reading.

Current implementation simply overwrites the pointer during profile dumping -- this won't work well with multi-threaded program -- after Values field is modified, runtime code may either crash or corrupt the data. Zerolized Value field may also be re-initialized with addresses which will be garbage in reading time. Introducing synchronization mechanism will greatly affect runtime performance.

The solution is simple -- instead of overwriting the "Data" data structure, the per-func data array will be copied to a small buffer and written out after the Values are fixed up in the buffer. The Data's Values field will be kept intact. There is no need to clear the memory either. In some use cases, the user code will just clear the counters and all the data allocated for VP can be reused.

[davidxl]

Patch rebase.

[betulb]

lib/profile/InstrProfilingFile.c

23

storek -> store ?

lib/profile/InstrProfilingValue.c

152 ↗

(On Diff #42457)

I do not think we really do need a DataValuePtrs array. I like the direction taken by the removal of the update of the Values field of the ProfileData struct, but I do not think this implementation makes the overall need for synchronization any less due to the global declaration of the DataValuePtr's array. This also resurfaces the comments made for a previous implementation i.e. "depending on the implicit ordering of the ProfileData nodes in memory for reading of ValueData nodes". Value profiling data is readable w/o this indirection. I do not think there is any need for this array.

[davidxl]

DataValuePtrs won't introduce data races as it is only accessed by the dumping thread.

Other than that, I admit I don't like introducing this overhead either. I will prepare a different patch for this.

[davidxl]

[Update the patch according to Betul's feedback)

By removing the dependency on ->Values field from the reader, the runtime patch now becomes quite clean. Lots of unnecessary things are removed:

1. The value profile data no longer needs to be put into an contiguous array before writing (as there will no relocation needed at read time)
2. This removes the need to compute the total size ahead of time.
3. It eliminates the problem of possible dropping of hot value sites due to updates from other threads
4. It eliminates the need to reserve extra bytes for buffer, thus the need to set reserved space at runtime
5. It greatly simplifies dumping -- there will be no need for two pass data collection -- one for total size, one for actual data collect.

The only major interface change is the data gathering interface -- it will now gather an array of pointers to ValueProfData objects instead of a pointer to the contiguous array.

[davidxl]

Any more comments? since this is a bug fix with good cleanups, I'd like to get this in sooner.

[betulb]

lib/profile/InstrProfilingValue.c

159 ↗

(On Diff #42541)

As an overall comment, I'm not too fond of using macros this heavily. Specific to this line, DEF_VALUE_RECORD is used only once and there is a macro definition for its contents. It's not necessary. Secondly, R is passed to the macro w/o being declared in this context. I'd rather have preferred that R is declared first and then passed to the macro (if macro usage is ever a requisite).

lib/profile/InstrProfilingWriter.c

76 ↗

(On Diff #42541)

I think there is an overhead of making the syscall to write as many times as there are profile data variables. I think it was one of the reasons why the other profiling constants/variables were merged into a single global variable and into linker sections to reduce the many iterations needed to write the data.

[davidxl]

lib/profile/InstrProfilingValue.c

159 ↗

(On Diff #42541)

yes, after the cleanup, this one can be removed -- as it is not reused anywhere else.

lib/profile/InstrProfilingWriter.c

76 ↗

(On Diff #42541)

We can do the write in batches of course. I will do some measurement to see if that is needed.

[betulb]

lib/profile/InstrProfilingFile.c

96

Is there a purpose for not directly using free, assigning it to a pointer and calling it through the function pointer?

lib/profile/InstrProfilingValue.c

181 ↗

(On Diff #42541)

Is there any need to return S in this implementation? We may also remove the need to pass the ValueDataSize around.

lib/profile/InstrProfilingWriter.c

68 ↗

(On Diff #42541)

Instead of ValueDataSize, why not check for if ValueDataBegin is null?

[davidxl]

lib/profile/InstrProfilingValue.c

159 ↗

(On Diff #42541)

For the record, this macro was also introduced to 'mimic' C++ where variable declaration and construction are done together.

181 ↗

(On Diff #42541)

good point. It was needed to indicate if there is vp data to be written -- but the rewrite makes it not necessary. Will remove.

lib/profile/InstrProfilingWriter.c

68 ↗

(On Diff #42541)

yes. Will change.

[davidxl]

Regarding performance, fwrite actually buffers the data so the number of system calls to write is actually much fewer than the number of Data entry - the overall time is dominated by IO, not system calls.

Here is the design of the stress testing:

1. total number of value data entries to be written out : 3 million
2. total size of the value data 1.6G -- this is way larger than an average program can produce -- for instance clang's profile data raw size is about 100M

Test machine is a sandybridge machine.

Results:
a) write out VP data one by one without batching

• total number of calls to fwrite: 3M,
• total number of calls to write: ~390K.
• real time: ~12s; sys time: ~2.5s

b) write out VP data in batches -- batch size is 1024 (i.e, copy 1024 VP data into a buffer and write out)

• total number of calls to fwrite: 3K
• total number of calls to write: ~6K (yes, it is more than calls to fwrite -- large a very large write can be split into smaller chunks).
• real time: ~12s, sys time: ~2s

The savings from reduced number of sys calls is not much.

In another experiment, /dev/null is used as the output to remove IO.

a) for non batch case

• real time: ~1.6s (average of 10 runs)
• sys time: ~0.85s (average of 10 runs)

b) with batch:

• real time: ~1.7s (average 10 runs)
• sys time: ~0.73s (average of 10 runs).

Note that b has addition cost of memory copy

Based on the above data, we can probably go with non-batch for simplicity for now. The batch write can be easily added later.

[davidxl]

Updated the patch according to Betul's feedback.

(VP gather interface is cleaned up -- the size is still needed by the header.)

[davidxl]

Reimplement VP data writing using the Buffer Writer API. With the new change, the VP writing buffer size also becomes configurable with an environment variable.

[davidxl]

Remove a redundant check.

[betulb]

LGTM overall.

lib/profile/InstrProfilingValue.c

135 ↗

(On Diff #43478)

nullptr check for ValueDataSize.

lib/profile/InstrProfilingWriter.c

65 ↗

(On Diff #43478)

1 -> sizeof(uint8_t) .

sizeof(char), sizeof(uint8_t) and imm constant value 1 are all interspersed throughout the code. sizeof(uint8_t) should replace all necessary locations to be consistent throughout the code. Similarly both char and uint8_t as types are used interchangeably throughout the code. Using one of the two consistently is preferable.

[davidxl]

Address review comments from Betul

lib/profile/InstrProfiling.c

if (!Mem)
     return 0;
   if (!BOOL_CMPXCHG(&Data->Values, 0, Mem)) {
     free(Mem);
     return 0;
   }
   return 1;
 }
 
-static void deallocateValueProfileCounters(__llvm_profile_data *Data) {
-  uint64_t NumVSites = 0, I;
-  uint32_t VKI;
-  if (!Data->Values)
-    return;
-  for (VKI = IPVK_First; VKI <= IPVK_Last; ++VKI)
-    NumVSites += Data->NumValueSites[VKI];
-  for (I = 0; I < NumVSites; I++) {
-    ValueProfNode *Node = ((ValueProfNode **)Data->Values)[I];
-    while (Node) {
-      ValueProfNode *Next = Node->Next;
-      free(Node);
-      Node = Next;
-    }
-  }
-  free(Data->Values);
-}
-
 LLVM_LIBRARY_VISIBILITY void
 __llvm_profile_instrument_target(uint64_t TargetValue, void *Data,
                                  uint32_t CounterIndex) {
 
   __llvm_profile_data *PData = (__llvm_profile_data *)Data;
   if (!PData)
     return;
 

 /* Extract the value profile data info from the runtime. */
 #define DEF_VALUE_RECORD(R, NS, V)                                             \
   ValueProfRuntimeRecord R;                                                    \
   if (initializeValueProfRuntimeRecord(&R, NS, V))                             \
     PROF_OOM_RETURN("Failed to write value profile data ");
 
 #define DTOR_VALUE_RECORD(R) finalizeValueProfRuntimeRecord(&R);
 
+void **DataValuePtrs LLVM_LIBRARY_VISIBILITY;
+
 LLVM_LIBRARY_VISIBILITY uint64_t
 __llvm_profile_gather_value_data(uint8_t **VDataArray) {
   size_t S = 0, RealSize = 0, BufferCapacity = 0, Extra = 0;
   __llvm_profile_data *I;
   if (!VDataArray)
     PROF_OOM_RETURN("Failed to write value profile data ");
 
   const __llvm_profile_data *DataEnd = __llvm_profile_end_data();
if (!S)
     return 0;
 
   Extra = getVprofExtraBytes();
   BufferCapacity = S + Extra;
   *VDataArray = calloc(BufferCapacity, sizeof(uint8_t));
   if (!*VDataArray)
     PROF_OOM_RETURN("Failed to write value profile data ");
 
+  size_t DataSize = DataEnd - DataBegin;
+  DataValuePtrs = calloc(DataSize, sizeof(void *));
+  if (!DataValuePtrs)
+    PROF_OOM_RETURN("Failed to write value profile data ");
+
   ValueProfData *VD = (ValueProfData *)(*VDataArray);
   /*
    * Extract value profile data and write into ValueProfData structure
    * one by one. Note that new value profile data added to any value
    * site (from another thread) after the ValueProfRuntimeRecord is
    * initialized (when the profile data snapshot is taken) won't be
    * collected. This is not a problem as those dropped value will have
    * very low taken count.
    */
   for (I = (__llvm_profile_data *)DataBegin; I != DataEnd; ++I) {
     DEF_VALUE_RECORD(R, I->NumValueSites, I->Values);
     if (getNumValueKindsRT(&R) == 0)
       continue;
 
     /* Record R has taken a snapshot of the VP data at this point. Newly
        added VP data for this function will be dropped.  */
     /* Check if there is enough space.  */
     if (BufferCapacity - RealSize < getValueProfDataSizeRT(&R)) {
       PROF_ERR("Value profile data is dropped :%s \n",
                "Out of buffer space. Use environment "
                " LLVM_VALUE_PROF_BUFFER_EXTRA to allocate more");
-      I->Values = 0;
     }
 
     serializeValueProfDataFromRT(&R, VD);
-    deallocateValueProfileCounters(I);
-    I->Values = VD;
+    DataValuePtrs[I - DataBegin] = VD;
     RealSize += VD->TotalSize;
     VD = (ValueProfData *)((char *)VD + VD->TotalSize);
     DTOR_VALUE_RECORD(R);
   }
 
   return RealSize;
 }

lib/profile/InstrProfilingFile.c

 #include "InstrProfilingUtil.h"
 #include <errno.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 
 #define UNCONST(ptr) ((void *)(uintptr_t)(ptr))
 
+#define BUFFSIZE 1024
+extern void **DataValuePtrs;
+
+/* The Values field of __llvm_profile_data structure is used to storek runtime
+ * ValueProfNode data pointers which is not what needs to be written out
+ * to the disk. Do the fix up before writing.
+ */
+static uint32_t writePerFuncData(const __llvm_profile_data *DataBegin,
+                                 uint32_t ItemSize, uint32_t NumData,
+                                 FILE *File) {
+  __llvm_profile_data *Buffer;
+  uint32_t RemainItem = NumData, CurIndex = 0;
+  /* Same sanity check.  */
+  if (ItemSize != sizeof(__llvm_profile_data))
+    return 1;
+
+  if ((size_t)(__llvm_profile_end_data() - DataBegin) != NumData)
+    return 1;
+
+  if (!NumData)
+    return 0;
+
+  /* Allocate a small write buffer for ValuePtr field fix up before writing out.
+   */
+  Buffer = (__llvm_profile_data *)calloc(BUFFSIZE, ItemSize);
+  if (!Buffer)
+    return 1;
+
+  CurIndex = 0;
+  while (RemainItem) {
+    uint32_t I;
+    uint32_t ActualSize = (RemainItem > BUFFSIZE ? BUFFSIZE : RemainItem);
+    memcpy(&Buffer[CurIndex], &DataBegin[CurIndex], ActualSize * ItemSize);
+    /* Now patch the data */
+    for (I = 0; I < ActualSize; I++)
+      Buffer[CurIndex + I].Values = DataValuePtrs[CurIndex + I];
+
+    /* Now write out */
+    if (fwrite(&Buffer[CurIndex], ItemSize, ActualSize, File) != ActualSize) {
+      free(Buffer);
+      return 1;
+    }
+
+    RemainItem -= ActualSize;
+    CurIndex += ActualSize;
+  }
+
+  free(Buffer);
+  free(DataValuePtrs);
+  return 0;
+}
+
 /* Return 1 if there is an error, otherwise return  0.  */
 static uint32_t fileWriter(ProfDataIOVec *IOVecs, uint32_t NumIOVecs,
                            void **WriterCtx) {
   uint32_t I;
   FILE *File = (FILE *)*WriterCtx;
   for (I = 0; I < NumIOVecs; I++) {
-    if (fwrite(IOVecs[I].Data, IOVecs[I].ElmSize, IOVecs[I].NumElm, File) !=
-        IOVecs[I].NumElm)
+    if (IOVecs[I].Data == __llvm_profile_begin_data() && DataValuePtrs != 0) {
+      if (writePerFuncData(IOVecs[I].Data, IOVecs[I].ElmSize, IOVecs[I].NumElm,
+                           File))
+        return 1;
+    } else if (fwrite(IOVecs[I].Data, IOVecs[I].ElmSize, IOVecs[I].NumElm,
+                      File) != IOVecs[I].NumElm)
       return 1;
   }
   return 0;
 }
 
 static int writeFile(FILE *File) {
   uint8_t *ValueDataBegin = NULL;
   const uint64_t ValueDataSize =
       __llvm_profile_gather_value_data(&ValueDataBegin);
   int r = llvmWriteProfData(fileWriter, File, ValueDataBegin, ValueDataSize);
   free(ValueDataBegin);
   return r;
 }
 
 static int writeFileWithName(const char *OutputName) {
   int RetVal;
   FILE *OutputFile;
   if (!OutputName || !OutputName[0])
     return -1;
 
   /* Append to the file to support profiling multiple shared objects. */
static void truncateCurrentFile(void) {
   if (!File)
     return;
   fclose(File);
 }
 
 static void setFilename(const char *Filename, int OwnsFilename) {
   /* Check if this is a new filename and therefore needs truncation. */
   int NewFile = !__llvm_profile_CurrentFilename ||
                 (Filename && strcmp(Filename, __llvm_profile_CurrentFilename));
   if (__llvm_profile_OwnsFilename)
     free(UNCONST(__llvm_profile_CurrentFilename));
 
   __llvm_profile_CurrentFilename = Filename;
   __llvm_profile_OwnsFilename = OwnsFilename;
 
   /* If not a new file, append to support profiling multiple shared objects. */
   if (NewFile)