Adjust some id bit shifts to fit inside 32 bit integers

[lanza]

Summary

The DAP on vscode uses a JavaScript number for identifiers while the
Visual Studio version uses a C# Int for identifiers. lldb-vscode is
bit shifting identifiers 32 bits to form a unique ID. Change this to
a 16 bit shift to allow the data to fit into 32 bits.

[lanza]

There should be quite a few more things switched to 32bit values to account for this. I've added that to my tasks. Putting this up just because this breaks functionality on Visual Studio.

[clayborg]

This won't work when we have many frames. If you get a stack trace that blows the stack, you can easily have 300K stack frames. Thread index ID can get quite high too. There are also no lifetimes on the frame IDs we use, so we never get told to free a frame ID when the IDE is done with one. So we either have to switch to using a map that can map between frame ID and lldb::SBFrame or let the map just grow and grow, or something else. This isn't sufficient.

[lanza]

@clayborg We can either store a dap-frame-to-lldb-frame map as well as a lldb-frame-to-dap-frame map or we can truncate the thread count down to a much smaller count of bits. I think the former is an ugly idea to just let a pair of gigantic maps grow endlessly over the lifetime of a program. E.G. for debugging some game that could be running for a long duration. For the latter, I haven't seen a thousand thread program before and if you're using a thousand threads you probably have much bigger problems than your GUI debugger. How about a split with 10 or so bits for the thread ID and the remaining 22 bits for the frame ID?

As per the breakpoint situation, I think we could do something similar with the breakpoint ID taking 10 bits and the BreakpointLocation ID taking 22 bits since a user likely isn't going to provide 1000 chosen breakpoints anyways.

[clayborg]

In D53599#1288214, @lanza wrote:

@clayborg We can either store a dap-frame-to-lldb-frame map as well as a lldb-frame-to-dap-frame map or we can truncate the thread count down to a much smaller count of bits. I think the former is an ugly idea to just let a pair of gigantic maps grow endlessly over the lifetime of a program. E.G. for debugging some game that could be running for a long duration. For the latter, I haven't seen a thousand thread program before and if you're using a thousand threads you probably have much bigger problems than your GUI debugger. How about a split with 10 or so bits for the thread ID and the remaining 22 bits for the frame ID?

2^19 = 524288
2^13 = 8192

Not many OSs can get a half million stack frames without running out of stack. So how about 19 bits for frame ID and 13 for the thread ID?

As per the breakpoint situation, I think we could do something similar with the breakpoint ID taking 10 bits and the BreakpointLocation ID taking 22 bits since a user likely isn't going to provide 1000 chosen breakpoints anyways.

Sounds good

[lanza]

adjust the shifts

[lanza]

update

[lanza]

formating

[clayborg]

tools/lldb-vscode/LLDBUtils.cpp

78–96

It would be nice to make all encoding and decoding into functions here. I would suggest also making:

#define THREAD_INDEX_SHIFT 19
int64_t MakeVSCodeFrameID(lldb::SBFrame &frame) {
  return (int64_t)(frame.GetThread().GetIndexID() << THREAD_INDEX_SHIFT | frame.GetFrameID());
}
uint32_t GetLLDBThreadIndexID(int64_t frame_id) {
  return frame_id >> THREAD_INDEX_SHIFT;
}
uint32_t GetLLDBFrameIndex(int64_t frame_id) {
  return frame_id & ((1u << THREAD_INDEX_SHIFT) - 1);
}

tools/lldb-vscode/VSCode.cpp

311–312

lldb::SBThread thread = process.GetThreadByIndexID(GetLLDBThreadIndexID(frame_id));

314

return thread.GetFrameAtIndex(GetLLDBFrameIndex(frame_id));

[lanza]

Am I missing some line of code or does lldb-vscode not ever map from the DAP breakpoint ID back to the LLDB BreakpointLocation and Breakpoint IDs? I wrote the equivalent functions but there doesn't seem to be anywhere that maps in the inverse direction.

[lanza]

add functions that handle the bit shifting

[lanza]

clang-format

[clayborg]

In D53599#1289691, @lanza wrote:

Am I missing some line of code or does lldb-vscode not ever map from the DAP breakpoint ID back to the LLDB BreakpointLocation and Breakpoint IDs? I wrote the equivalent functions but there doesn't seem to be anywhere that maps in the inverse direction.

Yeah, it is not ever mapped back. I believe the ID is sent back later, but it isn't used right now. When you have breakpoints set in a source file by file and line, they send one breakpoint request with multiple lines, and when a breakpoint is removed, they just send another packet with all source file and line breakpoints and you are expected to just "figure it out". Kind of lame, but it is what we have.

tools/lldb-vscode/LLDBUtils.cpp

68

"static constexpr" if we aren't going to use a #define statement

78

We should rename this to MakeDAPFrameID to match other functions.

[clayborg]

Just rename MakeVSCodeFrameID to MakeDAPFrameID, or rename all MakeDAPXXX functions you added to be MakeVSCodeXXX.

[lanza]

update

tools/lldb-vscode/JSONUtils.cpp

 llvm::json::Value CreateBreakpoint(lldb::SBBreakpointLocation &bp_loc) {
   // Each breakpoint location is treated as a separate breakpoint for VS code.
   // They don't have the notion of a single breakpoint with multiple locations.
   llvm::json::Object object;
   if (!bp_loc.IsValid())
     return llvm::json::Value(std::move(object));
 
   object.try_emplace("verified", true);
-  const auto bp_id = bp_loc.GetBreakpoint().GetID();
-  const auto vs_id = (int64_t)(((int64_t)bp_id << 32) | bp_loc.GetID());
+  const auto vs_id = MakeDAPBreakpointID(bp_loc);
   object.try_emplace("id", vs_id);
   auto bp_addr = bp_loc.GetAddress();
   if (bp_addr.IsValid()) {
     auto line_entry = bp_addr.GetLineEntry();
     const auto line = line_entry.GetLine();
     if (line != UINT32_MAX)
       object.try_emplace("line", line);
     object.try_emplace("source", CreateSource(line_entry));

tools/lldb-vscode/LLDBUtils.h

 ///     The LLDB stack frame object generate the ID for
 ///
 /// @return
 ///     A unique integer that allows us to easily find the right
 ///     stack frame within a thread on subsequent VS code requests.
 //----------------------------------------------------------------------
 int64_t MakeVSCodeFrameID(lldb::SBFrame &frame);
 
+///----------------------------------------------------------------------
+/// Given a DAP frame ID, convert to a LLDB thread index id.
+///
+/// VSCode requires a Stackframe "id" to be unique, so we use the frame
+/// index in the lower THREAD_INDEX_SHIFT bits and the thread index ID in
+/// the upper 32 - THREAD_INDEX_SHIFT bits.
+///
+/// @param[in] dap_frame_id
+///     The DAP frame ID to convert to a thread index ID.
+///
+/// @return
+///     The LLDB thread index ID.
+//----------------------------------------------------------------------
+uint32_t GetLLDBThreadIndexID(uint64_t dap_frame_id);
+
+///----------------------------------------------------------------------
+/// Given a DAP frame ID, convert to a LLDB frame ID.
+///
+/// VSCode requires a Stackframe "id" to be unique, so we use the frame
+/// index in the lower THREAD_INDEX_SHIFT bits and the thread index ID in
+/// the upper 32 - THREAD_INDEX_SHIFT bits.
+///
+/// @param[in] dap_frame_id
+///     The DAP frame ID to convert to a frame ID.
+///
+/// @return
+///     The LLDB frame index ID.
+//----------------------------------------------------------------------
+uint32_t GetLLDBFrameID(uint64_t dap_frame_id);
+
+///----------------------------------------------------------------------
+/// Given a LLDB breakpoint, make a breakpoint ID that is unique to a
+/// specific breakpoint and breakpoint location.
+///
+/// DAP requires a Breakpoint "id" to be unique, so we use the
+/// breakpoint ID in the lower BREAKPOINT_ID_SHIFT bits and the
+/// breakpoint location ID in the upper BREAKPOINT_ID_SHIFT bits.
+///
+/// @param[in] frame
+///     The LLDB stack frame object generate the ID for
+///
+/// @return
+///     A unique integer that allows us to easily find the right
+///     stack frame within a thread on subsequent VS code requests.
+//----------------------------------------------------------------------
+int64_t MakeDAPBreakpointID(lldb::SBBreakpointLocation &bp_loc);
+
+///----------------------------------------------------------------------
+/// Given a DAP breakpoint ID, convert to a LLDB breakpoint ID.
+///
+/// DAP requires a Breakpoint "id" to be unique, so we use the
+/// breakpoint ID in the lower BREAKPOINT_ID_SHIFT bits and the
+/// breakpoint location ID in the upper BREAKPOINT_ID_SHIFT bits.
+///
+/// @param[in] dap_breakpoint_id
+///     The DAP breakpoint ID to convert to an LLDB breakpoint ID.
+///
+/// @return
+///     The LLDB breakpoint ID.
+//----------------------------------------------------------------------
+uint32_t GetLLDBBreakpointID(uint64_t dap_breakpoint_id);
+
+///----------------------------------------------------------------------
+/// Given a DAP breakpoint ID, convert to a LLDB breakpoint location ID.
+///
+/// DAP requires a Breakpoint "id" to be unique, so we use the
+/// breakpoint ID in the lower BREAKPOINT_ID_SHIFT bits and the
+/// breakpoint location ID in the upper BREAKPOINT_ID_SHIFT bits.
+///
+/// @param[in] dap_breakpoint_id
+///     The DAP frame ID to convert to a breakpoint location ID.
+///
+/// @return
+///     The LLDB breakpoint location ID.
+//----------------------------------------------------------------------
+uint32_t GetLLDBBreakpointLocationID(uint64_t dap_breakpoint_id);
 } // namespace lldb_vscode
 
 #endif

tools/lldb-vscode/LLDBUtils.cpp

bool ThreadHasStopReason(lldb::SBThread &thread) {
   case lldb::eStopReasonThreadExiting:
   case lldb::eStopReasonInvalid:
   case lldb::eStopReasonNone:
     break;
   }
   return false;
 }
 
+static uint32_t const THREAD_INDEX_SHIFT = 19;
+
+uint32_t GetLLDBThreadIndexID(uint64_t dap_frame_id) {
+  return dap_frame_id >> THREAD_INDEX_SHIFT;
+}
+
+uint32_t GetLLDBFrameID(uint64_t dap_frame_id) {
+  return dap_frame_id & ((1u << THREAD_INDEX_SHIFT) - 1);
+}
+
 int64_t MakeVSCodeFrameID(lldb::SBFrame &frame) {
-  return (int64_t)frame.GetThread().GetIndexID() << 32 |
-         (int64_t)frame.GetFrameID();
+  return (int64_t)(frame.GetThread().GetIndexID() << THREAD_INDEX_SHIFT |
+                   frame.GetFrameID());
+}
+
+static uint32_t const BREAKPOINT_ID_SHIFT = 22;
+
+uint32_t GetLLDBBreakpointID(uint64_t dap_breakpoint_id) {
+  return dap_breakpoint_id >> BREAKPOINT_ID_SHIFT;
+}
+
+uint32_t GetLLDBBreakpointLocationID(uint64_t dap_breakpoint_id) {
+  return dap_breakpoint_id & ((1u << BREAKPOINT_ID_SHIFT) - 1);
+}
+
+int64_t MakeDAPBreakpointID(lldb::SBBreakpointLocation &bp_loc) {
+  return (int64_t)(bp_loc.GetBreakpoint().GetID() << BREAKPOINT_ID_SHIFT |
+                   bp_loc.GetID());
 }
 
 } // namespace lldb_vscode

tools/lldb-vscode/VSCode.cpp

lldb::SBThread VSCode::GetLLDBThread(const llvm::json::Object &arguments) {
   auto tid = GetSigned(arguments, "threadId", LLDB_INVALID_THREAD_ID);
   return target.GetProcess().GetThreadByID(tid);
 }
 
 lldb::SBFrame VSCode::GetLLDBFrame(const llvm::json::Object &arguments) {
   const uint64_t frame_id = GetUnsigned(arguments, "frameId", UINT64_MAX);
   lldb::SBProcess process = target.GetProcess();
   // Upper 32 bits is the thread index ID
-  lldb::SBThread thread = process.GetThreadByIndexID(frame_id >> 32);
+  lldb::SBThread thread =
+      process.GetThreadByIndexID(GetLLDBThreadIndexID(frame_id));
   // Lower 32 bits is the frame index
-  return thread.GetFrameAtIndex(frame_id & 0xffffffffu);
+  return thread.GetFrameAtIndex(GetLLDBFrameID(frame_id));
 }
 
 llvm::json::Value VSCode::CreateTopLevelScopes() {
   llvm::json::Array scopes;
   scopes.emplace_back(CreateScope("Locals", VARREF_LOCALS, num_locals, false));
   scopes.emplace_back(
       CreateScope("Globals", VARREF_GLOBALS, num_globals, false));
   scopes.emplace_back(CreateScope("Registers", VARREF_REGS, num_regs, false));