[WIP PATCH] PR23407 WIP: stapbpf support for strings as first class values

[WIP PATCH] PR23407 WIP: stapbpf support for strings as first class values

[Serhei Makarov]

Not committing this yet due to yet-lingering bugs, but this is what I've been working on recently. Decided to share it since I've eliminated all regressions in the existing testcases.

===

This is a basic patch which defines the STR value_type, denoting
string constants, which are lowered to pointers to literal strings on
the stack by a pass in bpf-opt.cxx. Currently, space for strings is
allocated using the program::use_tmp_space() mechanism. More than
one string literal can be stored on the stack at a time.

Limitations are 256 bytes for format strings, 64 bytes for other strings.

TODO: The code to allocate literal strings can later be integrated
with register allocation, in order to make more efficient use of
limited (512 bytes) stack space. Currently it's a bit greedy.

The next step is to support storing strings in global data structures
(bpf maps). Since bpf map helpers automatically copy data from the stack
to the map value, this should not be difficult to accomplish.

* bpf-internal.h (BPF_MAXSTRINGLEN, BPF_MAXFORMATLEN): New defines.
(enum value::value_type): New value_type STR denoting string constant.
(value::str_val): New field.
(value::value): Add option to set str_val.
(value::mk_str): New method.
(value::is_str): New method.
(value::str): New method.
(program::str_map): New field.
(program::new_str): New method.
* bpf-base.cxx (value::print): Print STR values.
(program::~program): XXX Should clean up str_map.
(program::new_str): New method.

* bpf-opt.cxx (emit_literal_string): Allocate space for a string
literal on the stack, then emit code to store the string in 4-byte chunks.
(lower_str_values): New function. See explanation at the top of the
commit message.
(program::generate): Add lower_str_values pass.
* bpf-translate.cxx (struct bpf_unparser): triage required visitor
functions by comparison with translate.cxx.
(translate_escapes): New function.
(visit_literal_string): New function, convert literal string to STR value.
(visit_compound_expression): BONUS - trying an implementation of this.
(visit_print_format): Create an STR value instead of emitting the
format string code immediately.

* stapbpf/bpfinterp.cxx (remove_tag): Added sanity check while debugging.

* testsuite/systemtap.bpf/bpf_tests/string1.stp: New file (WIP).
---
 bpf-base.cxx                                  |  18 ++++
 bpf-internal.h                                |  23 ++++-
 bpf-opt.cxx                                   |  82 +++++++++++++++++-
 bpf-translate.cxx                             | 120 +++++++++++++++++++-------
 stapbpf/bpfinterp.cxx                         |   1 +
 testsuite/systemtap.bpf/bpf_tests/string1.stp |  31 +++++++
 6 files changed, 237 insertions(+), 38 deletions(-)
 create mode 100644 testsuite/systemtap.bpf/bpf_tests/string1.stp

diff --git a/bpf-base.cxx b/bpf-base.cxx
index 167eb7f1e..e44cdeee3 100644
--- a/bpf-base.cxx
+++ b/bpf-base.cxx
@@ -10,6 +10,7 @@
 #include "bpf-internal.h"
 #include "elaborate.h"
 #include "session.h"
+#include "util.h"
 
 using namespace std;
 
@@ -24,6 +25,8 @@ value::print(std::ostream &o) const
       return o << "#";
     case IMM:
       return o << "$" << imm_val;
+    case STR:
+      return o << "$\"" << escaped_literal_string (str_val) << "\"";
     case HARDREG:
       return o << "r" << reg_val;
     case TMPREG:
@@ -528,6 +531,8 @@ program::~program()
     delete *i;
   for (auto i = imm_map.begin (); i != imm_map.end (); ++i)
     delete i->second;
+  for (auto i = str_map.begin (); i != str_map.end (); ++i)
+    delete i->second;
   #endif
 }
 
@@ -570,6 +575,19 @@ program::new_imm(int64_t i)
   return v;
 }
 
+value *
+program::new_str(std::string str)
+{
+  auto old = str_map.find(str);
+  if (old != str_map.end())
+    return old->second;
+
+  value *v = new value(value::mk_str(str));
+  auto ok = str_map.insert(std::pair<std::string, value *>(str, v));
+  assert(ok.second);
+  return v;
+}
+
 void
 program::mk_ld(insn_inserter &ins, int sz, value *dest, value *base, int off)
 {
diff --git a/bpf-internal.h b/bpf-internal.h
index f63385a6a..bfb33dec6 100644
--- a/bpf-internal.h
+++ b/bpf-internal.h
@@ -28,8 +28,10 @@ struct vardecl;
 namespace bpf {
 
 #define MAX_BPF_STACK 512
-#define BPF_MAXSTRINGLEN 64 // TODO: For strings as first-class values.
+#define BPF_MAXSTRINGLEN 64
+#define BPF_MAXFORMATLEN 256
 #define BPF_REG_SIZE 8
+// TODO: BPF_MAX{STRING,FORMAT}LEN should be user-configurable.
 
 typedef unsigned short regno;
 static const regno max_regno = BPF_MAXINSNS;
@@ -48,24 +50,33 @@ enum condition
 
 struct value
 {
-  enum value_type { UNINIT, IMM, HARDREG, TMPREG };
+  enum value_type { UNINIT,
+                    IMM,
+                    STR, /* <- lowered to HARDREG by the optimizer */
+                    HARDREG,
+                    TMPREG, /* <- lowered to HARDREG by the optimizer */ };
 
   value_type type	: 16;
   regno reg_val		: 16;
   int64_t imm_val;
+  std::string str_val;
 
-  value(value_type t = UNINIT, regno r = noreg, int64_t c = 0)
-    : type(t), reg_val(r), imm_val(c)
+  value(value_type t = UNINIT, regno r = noreg, int64_t c = 0, std::string s = "")
+    : type(t), reg_val(r), imm_val(c), str_val(s)
   { }
 
   static value mk_imm(int64_t i) { return value(IMM, noreg, i); }
+  static value mk_str(std::string s) { return value(STR, noreg, 0, s); }
   static value mk_reg(regno r) { return value(TMPREG, r); }
   static value mk_hardreg(regno r) { return value(HARDREG, r); }
 
   bool is_reg() const { return type >= HARDREG; }
   bool is_imm() const { return type == IMM; }
+  bool is_str() const { return type == STR; }
+
   regno reg() const { assert(is_reg()); return reg_val; }
   int64_t imm() const { assert(is_imm()); return imm_val; }
+  std::string str() const { assert(is_str()); return str_val; }
 
   std::ostream& print(std::ostream &) const;
 };
@@ -205,12 +216,16 @@ struct program
 
   std::vector<value> hardreg_vals;
   std::vector<value *> reg_vals;
+
+  // Store at most one of each IMM and STR value:
   std::unordered_map<int64_t, value *> imm_map;
+  std::unordered_map<std::string, value *> str_map;
 
   regno max_reg() const { return reg_vals.size() + MAX_BPF_REG; }
   value *lookup_reg(regno r);
   value *new_reg();
   value *new_imm(int64_t);
+  value *new_str(std::string);
 
   // The BPF local stack is [0, -512] indexed off BPF_REG_10.
   // The translator has dibs on the low bytes, [0, -max_tmp_space],
diff --git a/bpf-opt.cxx b/bpf-opt.cxx
index cbbbc8db5..d0bffacf6 100644
--- a/bpf-opt.cxx
+++ b/bpf-opt.cxx
@@ -17,6 +17,81 @@
 
 namespace bpf {
 
+// Write a string literal out to the stack in 4-byte chunks.
+//
+// ??? Could use 8-byte chunks if we're starved for instruction counts.
+// ??? Endianness of the target comes into play here.
+static value *
+emit_literal_string(program &p, insn_inserter &ins, value *val)
+{
+  // Append the string to existing temporary data.
+  //
+  // TODO: This could produce significant size limitations.
+  // A better solution would be to integrate with the
+  // register allocator and reclaim the space after
+  // the string literal is no longer live.
+  size_t str_off = p.max_tmp_space;
+  str_off += 4 - str_off % 4; // verifier requires rounding to nearest multiple of 4
+  p.use_tmp_space(str_off);
+
+  std::string str = val->str();
+  size_t str_bytes = str.size() + 1;
+  size_t str_words = (str_bytes + 3) / 4;
+  if (str_off + str_bytes > MAX_BPF_STACK)
+    throw std::runtime_error("string allocation failed due to lack of room on stack");
+
+  value *frame = p.lookup_reg(BPF_REG_10);
+  for (unsigned i = 0; i < str_words; ++i)
+    {
+      uint32_t word = 0;
+      for (unsigned j = 0; j < 4; ++j)
+        if (i * 4 + j < str_bytes - 1)
+          {
+            // ??? little-endian target
+            word |= (uint32_t)str[i * 4 + j] << (j * 8);
+          }
+      p.mk_st(ins, BPF_W, frame,
+              (int32_t)(-str_words + i) * 4 + (-str_off),
+              p.new_imm(word));
+    }
+  p.max_tmp_space += str_bytes; // add to existing space!
+
+  value *out = p.new_reg();
+  p.mk_binary(ins, BPF_ADD, out,
+              frame, p.new_imm(-(int32_t)str_words * 4 - (int32_t)str_off));
+  return out;
+}
+
+static void
+lower_str_values(program &p)
+{
+  const unsigned nblocks = p.blocks.size();
+
+  for (unsigned i = 0; i < nblocks; ++i)
+    {
+      block *b = p.blocks[i];
+
+      for (insn *j = b->first; j != NULL; j = j->next)
+        {
+          value *s0 = j->src0;
+          if (s0 && s0->is_str())
+            {
+              insn_before_inserter ins(b, j);
+              value *new_s0 = emit_literal_string(p, ins, s0);
+              j->src0 = new_s0;
+            }
+
+          value *s1 = j->src1;
+          if (s1 && s1->is_str())
+            {
+              insn_before_inserter ins(b, j);
+              value *new_s1 = emit_literal_string(p, ins, s1);
+              j->src1 = new_s1;
+            }
+        }
+    }
+}
+
 static void
 fixup_operands(program &p)
 {
@@ -758,7 +833,7 @@ finalize_allocation(std::vector<regno> &partition, program &p)
 
       // Hard registers are partition[i] == i,
       // and while other partition members should require
-      // no more than three dereferences to yeild a hard reg,
+      // no more than three dereferences to yield a hard reg,
       // we allow for up to ten dereferences.
       unsigned r = partition[i];
       for (int j = 0; r >= MAX_BPF_REG && j < 10; j++)
@@ -804,7 +879,7 @@ reg_alloc(program &p)
 
       merge(partition, ordered, life, igraph, p);
 
-      // ??? Use C++14 lambda.
+      // XXX: Consider using C++14 lambda.
       pref_sort_reg sort_obj(life);
       std::sort(ordered.begin(), ordered.end(), sort_obj);
 
@@ -875,12 +950,13 @@ post_alloc_cleanup (program &p)
 void
 program::generate()
 {
+  lower_str_values(*this);
   fixup_operands(*this);
   thread_jumps(*this);
   fold_jumps(*this);
   reorder_blocks(*this);
   reg_alloc(*this);
-  post_alloc_cleanup (*this);
+  post_alloc_cleanup(*this);
 }
 
 } // namespace bpf
diff --git a/bpf-translate.cxx b/bpf-translate.cxx
index cfa2c2a56..c2bb6f1c2 100644
--- a/bpf-translate.cxx
+++ b/bpf-translate.cxx
@@ -172,34 +172,58 @@ struct bpf_unparser : public throwing_visitor
   block *get_ret0_block();
   block *get_exit_block();
 
+  // TODO General triage of bpf-possible functionality:
   virtual void visit_block (::block *s);
-  virtual void visit_embeddedcode (embeddedcode *s);
+  // TODO visit_try_block -> UNHANDLED
+  virtual void visit_embeddedcode (embeddedcode *s); // TODO need to find testcase/example for this
   virtual void visit_null_statement (null_statement *s);
   virtual void visit_expr_statement (expr_statement *s);
   virtual void visit_if_statement (if_statement* s);
   virtual void visit_for_loop (for_loop* s);
   virtual void visit_foreach_loop (foreach_loop* s);
   virtual void visit_return_statement (return_statement* s);
+  virtual void visit_delete_statement (delete_statement* s);
+  // TODO visit_next_statement -> UNHANDLED
   virtual void visit_break_statement (break_statement* s);
   virtual void visit_continue_statement (continue_statement* s);
-  virtual void visit_delete_statement (delete_statement* s);
+  virtual void visit_literal_string (literal_string *e);
   virtual void visit_literal_number (literal_number* e);
+  // TODO visit_embedded_expr -> UNHANDLED, could be handled like embedded_code with a return value?
   virtual void visit_binary_expression (binary_expression* e);
   virtual void visit_unary_expression (unary_expression* e);
   virtual void visit_pre_crement (pre_crement* e);
   virtual void visit_post_crement (post_crement* e);
   virtual void visit_logical_or_expr (logical_or_expr* e);
   virtual void visit_logical_and_expr (logical_and_expr* e);
+  virtual void visit_array_in (array_in* e);
+  // ??? visit_regex_query is UNHANDLED, requires adding new kernel functionality.
+  virtual void visit_compound_expression (compound_expression *e);
   virtual void visit_comparison (comparison* e);
+  // TODO visit_concatenation -> (2) pseudo-LOOP: copy the strings while concatenating
   virtual void visit_ternary_expression (ternary_expression* e);
   virtual void visit_assignment (assignment* e);
   virtual void visit_symbol (symbol* e);
+  virtual void visit_target_register (target_register* e);
+  virtual void visit_target_deref (target_deref* e);
+  // visit_target_bitfield -> ?? should already be handled in earlier pass?
+  // visit_target_symbol -> ?? should already be handled in earlier pass
   virtual void visit_arrayindex (arrayindex *e);
-  virtual void visit_array_in (array_in* e);
   virtual void visit_functioncall (functioncall* e);
   virtual void visit_print_format (print_format* e);
-  virtual void visit_target_register (target_register* e);
-  virtual void visit_target_deref (target_deref* e);
+  // TODO visit_stat_op -> (3) possibly userspace-only :: get the correct stat value out of BPF_MAP_TYPE_PERCPU_?
+  // TODO visit_hist_op -> implement as a userspace-only helper
+  // visit_atvar_op -> ?? should already be handled in earlier pass
+  // visit_cast_op -> ?? should already be handled in earlier pass
+  // visit_autocast_op -> ?? should already be handled in earlier pass
+  // visit_defined_op -> ?? should already be handled in earlier pass
+  // visit_entry_op -> ?? should already be handled in earlier pass
+  // visit_perf_op -> ?? should already be handled in earlier pass
+
+  // TODO: Other bpf functionality to take advantage of in tapsets, or as alternate implementations:
+  // - backtrace.stp :: BPF_MAP_TYPE_STACKTRACE + bpf_getstackid
+  // - BPF_MAP_TYPE_LRU_HASH :: for size-limited maps
+  // - BPF_MAP_GET_NEXT_KEY :: for user-space iteration through maps
+  // see https://ferrisellis.com/posts/ebpf_syscall_and_maps/#ebpf-map-types
 
   void emit_stmt(statement *s);
   void emit_mov(value *d, value *s);
@@ -973,6 +997,49 @@ bpf_unparser::visit_delete_statement (delete_statement *s)
   throw SEMANTIC_ERROR (_("unknown lvalue"), e->tok);
 }
 
+// TODO: Move to a logical location.
+// Translate string escape characters.
+std::string
+translate_escapes (interned_string &str)
+{
+  std::string result;
+  bool saw_esc = false;
+  for (interned_string::const_iterator j = str.begin();
+       j != str.end(); ++j)
+    {
+      if (saw_esc)
+        {
+          saw_esc = false;
+          switch (*j)
+            {
+            case 'f': result += '\f'; break;
+            case 'n': result += '\n'; break;
+            case 'r': result += '\r'; break;
+            case 't': result += '\t'; break;
+            case 'v': result += '\v'; break;
+            default:  result += *j; break;
+            }
+        }
+      else if (*j == '\\')
+        saw_esc = true;
+      else
+        result += *j;
+    }
+  return result;
+}
+
+void
+bpf_unparser::visit_literal_string (literal_string* e)
+{
+  interned_string v = e->value;
+  std::string str = translate_escapes(v);
+
+  size_t str_bytes = str.size() + 1;
+  if (str_bytes > BPF_MAXSTRINGLEN)
+    throw SEMANTIC_ERROR(_("String literal too long"), e->tok);
+  result = this_prog.new_str(str); // will be lowered to a pointer by bpf-opt.cxx
+}
+
 void
 bpf_unparser::visit_literal_number (literal_number* e)
 {
@@ -1103,6 +1170,14 @@ bpf_unparser::visit_logical_and_expr (logical_and_expr* e)
   result = emit_bool (e);
 }
 
+// TODO: This matches translate.cxx, but it looks like the functionality is disabled in the parser.
+void
+bpf_unparser::visit_compound_expression (compound_expression* e)
+{
+  e->left->visit(this);
+  e->right->visit(this); // overwrite result of first expression
+}
+
 void
 bpf_unparser::visit_comparison (comparison* e)
 {
@@ -1821,30 +1896,8 @@ bpf_unparser::visit_print_format (print_format *e)
     {
       // ??? If this is a long string with no actual arguments,
       // intern the string as a global and use "%s" as the format.
-      // Translate string escape characters.
       interned_string fstr = e->raw_components;
-      bool saw_esc = false;
-      for (interned_string::const_iterator j = fstr.begin();
-	   j != fstr.end(); ++j)
-	{
-	  if (saw_esc)
-	    {
-	      saw_esc = false;
-	      switch (*j)
-		{
-		case 'f': format += '\f'; break;
-		case 'n': format += '\n'; break;
-		case 'r': format += '\r'; break;
-		case 't': format += '\t'; break;
-		case 'v': format += '\v'; break;
-		default:  format += *j; break;
-		}
-	    }
-	  else if (*j == '\\')
-	    saw_esc = true;
-	  else
-	    format += *j;
-	}
+      format += translate_escapes(fstr);
     }
   else
     {
@@ -1890,12 +1943,16 @@ bpf_unparser::visit_print_format (print_format *e)
     }
 
   // The bpf verifier requires that the format string be stored on the
-  // bpf program stack.  Write it out in 4 byte units.
-  // ??? Endianness of the target comes into play here.
+  // bpf program stack.  This is handled by bpf-opt.cxx lowering STR values.
   size_t format_bytes = format.size() + 1;
   if (format_bytes > 256)
     throw SEMANTIC_ERROR(_("Format string for print too long"), e->tok);
-
+#if 1
+  this_prog.mk_mov(this_ins, this_prog.lookup_reg(BPF_REG_1),
+                   this_prog.new_str(format));
+#endif
+#if 0
+  // TODO: MOVED TO bpf-opt.cxx => emit_literal_str
   size_t format_words = (format_bytes + 3) / 4;
   value *frame = this_prog.lookup_reg(BPF_REG_10);
   for (i = 0; i < format_words; ++i)
@@ -1915,6 +1972,7 @@ bpf_unparser::visit_print_format (print_format *e)
 
   this_prog.mk_binary(this_ins, BPF_ADD, this_prog.lookup_reg(BPF_REG_1),
 		      frame, this_prog.new_imm(-(int32_t)format_words * 4));
+#endif
   emit_mov(this_prog.lookup_reg(BPF_REG_2), this_prog.new_imm(format_bytes));
   for (i = 0; i < nargs; ++i)
     emit_mov(this_prog.lookup_reg(BPF_REG_3 + i), actual[i]);
diff --git a/stapbpf/bpfinterp.cxx b/stapbpf/bpfinterp.cxx
index 5542938ed..fb4edaa43 100644
--- a/stapbpf/bpfinterp.cxx
+++ b/stapbpf/bpfinterp.cxx
@@ -65,6 +65,7 @@ remove_tag(const char *fstr)
   ++fstr;
   const char *end = fstr + strlen(fstr);
   while (*(--end) != '<');
+  assert(end >= fstr);
   return std::string(fstr, end - fstr);
 }
 
diff --git a/testsuite/systemtap.bpf/bpf_tests/string1.stp b/testsuite/systemtap.bpf/bpf_tests/string1.stp
new file mode 100644
index 000000000..12fa0ba60
--- /dev/null
+++ b/testsuite/systemtap.bpf/bpf_tests/string1.stp
@@ -0,0 +1,31 @@
+// stapbpf string manipulation -- store string in global data structure
+
+// TODO global var
+// TODO global tab1
+// TODO global tab2
+
+probe begin {
+  printf("BEGIN\n")
+  var = "str1"
+  // TODO tab1[0] = "str2"
+  // TODO tab2["key"] = "str3"
+  printf("[[%s]]\n", var) // TODO: temporary
+}
+
+probe kernel.function("vfs_read") {
+  var = "str1" // TODO: temporary
+  printf("[%s]\n", "str0")
+  printf("{%s}\n", var)
+  // TODO printf("<%s>\n", tab1[0])
+  // TODO printf("(%s)\n", tab2["key"])
+  exit()
+}
+
+probe end {
+  var = "str1" // TODO: temporary
+  printf("[%s]\n", "str0")
+  printf("{%s}\n", var)
+  // TODO printf("<%s>\n", tab1[0])
+  // TODO printf("(%s)\n", tab2["key"])
+  printf("END PASS\n") // TODO check output string in bpf.exp
+}
-- 
2.14.3