Merge #7806 from ZyX-I/list-stat

Add a way to collect list usage statistics

3 files changed, 232 insertions, 17 deletions

diff --git a/src/nvim/eval/decode.c b/src/nvim/eval/decode.c
index cd967ed5c5..17799b500c 100644
--- a/src/nvim/eval/decode.c
+++ b/src/nvim/eval/decode.c
@@ -150,7 +150,7 @@ static inline int json_decoder_pop(ValuesStackItem obj,
       }
       obj_di->di_tv = obj.val;
     } else {
-      list_T *const kv_pair = tv_list_alloc();
+      list_T *const kv_pair = tv_list_alloc(2);
       tv_list_append_list(last_container.special_val, kv_pair);
       tv_list_append_owned_tv(kv_pair, key.val);
       tv_list_append_owned_tv(kv_pair, obj.val);
@@ -221,13 +221,18 @@ static inline int json_decoder_pop(ValuesStackItem obj,
 /// Create a new special dictionary that ought to represent a MAP
 ///
 /// @param[out]  ret_tv  Address where new special dictionary is saved.
+/// @param[in]  len  Expected number of items to be populated before list
+///                  becomes accessible from VimL. It is still valid to
+///                  underpopulate a list, value only controls how many elements
+///                  will be allocated in advance. @see ListLenSpecials.
 ///
 /// @return [allocated] list which should contain key-value pairs. Return value
 ///                     may be safely ignored.
-list_T *decode_create_map_special_dict(typval_T *const ret_tv)
+list_T *decode_create_map_special_dict(typval_T *const ret_tv,
+                                       const ptrdiff_t len)
   FUNC_ATTR_NONNULL_ALL
 {
-  list_T *const list = tv_list_alloc();
+  list_T *const list = tv_list_alloc(len);
   tv_list_ref(list);
   create_special_dict(ret_tv, kMPMap, ((typval_T) {
     .v_type = VAR_LIST,
@@ -263,7 +268,7 @@ typval_T decode_string(const char *const s, const size_t len,
                               ? ((s != NULL) && (memchr(s, NUL, len) != NULL))
                               : (bool)hasnul);
   if (really_hasnul) {
-    list_T *const list = tv_list_alloc();
+    list_T *const list = tv_list_alloc(kListLenMayKnow);
     tv_list_ref(list);
     typval_T tv;
     create_special_dict(&tv, binary ? kMPBinary : kMPString, ((typval_T) {
@@ -843,7 +848,7 @@ json_decode_string_cycle_start:
         break;
       }
       case '[': {
-        list_T *list = tv_list_alloc();
+        list_T *list = tv_list_alloc(kListLenMayKnow);
         tv_list_ref(list);
         typval_T tv = {
           .v_type = VAR_LIST,
@@ -864,7 +869,7 @@ json_decode_string_cycle_start:
         list_T *val_list = NULL;
         if (next_map_special) {
           next_map_special = false;
-          val_list = decode_create_map_special_dict(&tv);
+          val_list = decode_create_map_special_dict(&tv, kListLenMayKnow);
         } else {
           dict_T *dict = tv_dict_alloc();
           dict->dv_refcount++;
@@ -964,7 +969,7 @@ int msgpack_to_vim(const msgpack_object mobj, typval_T *const rettv)
           .vval = { .v_number = (varnumber_T) mobj.via.u64 },
         };
       } else {
-        list_T *const list = tv_list_alloc();
+        list_T *const list = tv_list_alloc(4);
         tv_list_ref(list);
         create_special_dict(rettv, kMPInteger, ((typval_T) {
           .v_type = VAR_LIST,
@@ -987,7 +992,7 @@ int msgpack_to_vim(const msgpack_object mobj, typval_T *const rettv)
           .vval = { .v_number = (varnumber_T) mobj.via.i64 },
         };
       } else {
-        list_T *const list = tv_list_alloc();
+        list_T *const list = tv_list_alloc(4);
         tv_list_ref(list);
         create_special_dict(rettv, kMPInteger, ((typval_T) {
           .v_type = VAR_LIST,
@@ -1033,7 +1038,7 @@ int msgpack_to_vim(const msgpack_object mobj, typval_T *const rettv)
       break;
     }
     case MSGPACK_OBJECT_ARRAY: {
-      list_T *const list = tv_list_alloc();
+      list_T *const list = tv_list_alloc((ptrdiff_t)mobj.via.array.size);
       tv_list_ref(list);
       *rettv = (typval_T) {
         .v_type = VAR_LIST,
@@ -1085,9 +1090,10 @@ int msgpack_to_vim(const msgpack_object mobj, typval_T *const rettv)
       }
       break;
 msgpack_to_vim_generic_map: {}
-      list_T *const list = decode_create_map_special_dict(rettv);
+      list_T *const list = decode_create_map_special_dict(
+          rettv, (ptrdiff_t)mobj.via.map.size);
       for (size_t i = 0; i < mobj.via.map.size; i++) {
-        list_T *const kv_pair = tv_list_alloc();
+        list_T *const kv_pair = tv_list_alloc(2);
         tv_list_append_list(list, kv_pair);
 
         typval_T key_tv = { .v_type = VAR_UNKNOWN };
@@ -1107,10 +1113,10 @@ msgpack_to_vim_generic_map: {}
       break;
     }
     case MSGPACK_OBJECT_EXT: {
-      list_T *const list = tv_list_alloc();
+      list_T *const list = tv_list_alloc(2);
       tv_list_ref(list);
       tv_list_append_number(list, mobj.via.ext.type);
-      list_T *const ext_val_list = tv_list_alloc();
+      list_T *const ext_val_list = tv_list_alloc(kListLenMayKnow);
       tv_list_append_list(list, ext_val_list);
       create_special_dict(rettv, kMPExt, ((typval_T) {
         .v_type = VAR_LIST,
diff --git a/src/nvim/eval/typval.c b/src/nvim/eval/typval.c
index ac6c8c8aa6..c8b550f902 100644
--- a/src/nvim/eval/typval.c
+++ b/src/nvim/eval/typval.c
@@ -31,6 +31,7 @@
 #include "nvim/message.h"
 // TODO(ZyX-I): Move line_breakcheck out of misc1
 #include "nvim/misc1.h"  // For line_breakcheck
+#include "nvim/os/fileio.h"
 
 #ifdef INCLUDE_GENERATED_DECLARATIONS
 # include "eval/typval.c.generated.h"
@@ -45,6 +46,70 @@ bool tv_in_free_unref_items = false;
 const char *const tv_empty_string = "";
 
 //{{{1 Lists
+//{{{2 List log
+#ifdef LOG_LIST_ACTIONS
+ListLog *list_log_first = NULL;
+ListLog *list_log_last = NULL;
+
+/// Write list log to the given file
+///
+/// @param[in]  fname  File to write log to. Will be appended to if already
+///                    present.
+void list_write_log(const char *const fname)
+  FUNC_ATTR_NONNULL_ALL
+{
+  FileDescriptor fp;
+  const int fo_ret = file_open(&fp, fname, kFileCreate|kFileAppend, 0600);
+  if (fo_ret != 0) {
+    emsgf(_("E5142: Failed to open file %s: %s"), fname, os_strerror(fo_ret));
+    return;
+  }
+  for (ListLog *chunk = list_log_first; chunk != NULL;) {
+    for (size_t i = 0; i < chunk->size; i++) {
+      char buf[10 + 1 + ((16 + 3) * 3) + (8 + 2) + 2];
+      //       act  :     hex  " c:"      len "[]" "\n\0"
+      const ListLogEntry entry = chunk->entries[i];
+      const size_t snp_len = (size_t)snprintf(
+          buf, sizeof(buf),
+          "%-10.10s: l:%016" PRIxPTR "[%08d] 1:%016" PRIxPTR " 2:%016" PRIxPTR
+          "\n",
+          entry.action, entry.l, entry.len, entry.li1, entry.li2);
+      assert(snp_len + 1 == sizeof(buf));
+      const ptrdiff_t fw_ret = file_write(&fp, buf, snp_len);
+      if (fw_ret != (ptrdiff_t)snp_len) {
+        assert(fw_ret < 0);
+        if (i) {
+          memmove(chunk->entries, chunk->entries + i,
+                  sizeof(chunk->entries[0]) * (chunk->size - i));
+          chunk->size -= i;
+        }
+        emsgf(_("E5143: Failed to write to file %s: %s"),
+              fname, os_strerror((int)fw_ret));
+        return;
+      }
+    }
+    list_log_first = chunk->next;
+    xfree(chunk);
+    chunk = list_log_first;
+  }
+  const int fc_ret = file_close(&fp, true);
+  if (fc_ret != 0) {
+    emsgf(_("E5144: Failed to close file %s: %s"), fname, os_strerror(fc_ret));
+  }
+}
+
+#ifdef EXITFREE
+/// Free list log
+void list_free_log(void)
+{
+  for (ListLog *chunk = list_log_first; chunk != NULL;) {
+    list_log_first = chunk->next;
+    xfree(chunk);
+    chunk = list_log_first;
+  }
+}
+#endif
+#endif
 //{{{2 List item
 
 /// Allocate a list item
@@ -132,8 +197,14 @@ void tv_list_watch_fix(list_T *const l, const listitem_T *const item)
 ///
 /// Caller should take care of the reference count.
 ///
+/// @param[in]  len  Expected number of items to be populated before list
+///                  becomes accessible from VimL. It is still valid to
+///                  underpopulate a list, value only controls how many elements
+///                  will be allocated in advance. Currently does nothing.
+///                  @see ListLenSpecials.
+///
 /// @return [allocated] new list.
-list_T *tv_list_alloc(void)
+list_T *tv_list_alloc(const ptrdiff_t len)
   FUNC_ATTR_NONNULL_RET
 {
   list_T *const list = xcalloc(1, sizeof(list_T));
@@ -145,6 +216,7 @@ list_T *tv_list_alloc(void)
   list->lv_used_prev = NULL;
   list->lv_used_next = gc_first_list;
   gc_first_list = list;
+  list_log(list, NULL, (void *)(uintptr_t)len, "alloc");
   return list;
 }
 
@@ -174,6 +246,8 @@ void tv_list_init_static10(staticList10_T *const sl)
     li->li_prev = li - 1;
     li->li_next = li + 1;
   }
+  list_log((const list_T *)sl, &sl->sl_items[0], &sl->sl_items[SL_SIZE - 1],
+           "s10init");
 #undef SL_SIZE
 }
 
@@ -185,6 +259,7 @@ void tv_list_init_static(list_T *const l)
 {
   memset(l, 0, sizeof(*l));
   l->lv_refcount = DO_NOT_FREE_CNT;
+  list_log(l, NULL, NULL, "sinit");
 }
 
 /// Free items contained in a list
@@ -193,6 +268,7 @@ void tv_list_init_static(list_T *const l)
 void tv_list_free_contents(list_T *const l)
   FUNC_ATTR_NONNULL_ALL
 {
+  list_log(l, NULL, NULL, "freecont");
   for (listitem_T *item = l->lv_first; item != NULL; item = l->lv_first) {
     // Remove the item before deleting it.
     l->lv_first = item->li_next;
@@ -222,6 +298,7 @@ void tv_list_free_list(list_T *const l)
   if (l->lv_used_next != NULL) {
     l->lv_used_next->lv_used_prev = l->lv_used_prev;
   }
+  list_log(l, NULL, NULL, "freelist");
 
   xfree(l);
 }
@@ -266,6 +343,7 @@ void tv_list_drop_items(list_T *const l, listitem_T *const item,
                         listitem_T *const item2)
   FUNC_ATTR_NONNULL_ALL
 {
+  list_log(l, item, item2, "drop");
   // Notify watchers.
   for (listitem_T *ip = item; ip != item2->li_next; ip = ip->li_next) {
     l->lv_len--;
@@ -283,6 +361,7 @@ void tv_list_drop_items(list_T *const l, listitem_T *const item,
     item->li_prev->li_next = item2->li_next;
   }
   l->lv_idx_item = NULL;
+  list_log(l, l->lv_first, l->lv_last, "afterdrop");
 }
 
 /// Like tv_list_drop_items, but also frees all removed items
@@ -290,6 +369,7 @@ void tv_list_remove_items(list_T *const l, listitem_T *const item,
                           listitem_T *const item2)
   FUNC_ATTR_NONNULL_ALL
 {
+  list_log(l, item, item2, "remove");
   tv_list_drop_items(l, item, item2);
   for (listitem_T *li = item;;) {
     tv_clear(TV_LIST_ITEM_TV(li));
@@ -314,6 +394,7 @@ void tv_list_move_items(list_T *const l, listitem_T *const item,
                         const int cnt)
   FUNC_ATTR_NONNULL_ALL
 {
+  list_log(l, item, item2, "move");
   tv_list_drop_items(l, item, item2);
   item->li_prev = tgt_l->lv_last;
   item2->li_next = NULL;
@@ -324,6 +405,7 @@ void tv_list_move_items(list_T *const l, listitem_T *const item,
   }
   tgt_l->lv_last = item2;
   tgt_l->lv_len += cnt;
+  list_log(tgt_l, tgt_l->lv_first, tgt_l->lv_last, "movetgt");
 }
 
 /// Insert list item
@@ -352,6 +434,7 @@ void tv_list_insert(list_T *const l, listitem_T *const ni,
     }
     item->li_prev = ni;
     l->lv_len++;
+    list_log(l, ni, item, "insert");
   }
 }
 
@@ -378,6 +461,7 @@ void tv_list_insert_tv(list_T *const l, typval_T *const tv,
 void tv_list_append(list_T *const l, listitem_T *const item)
   FUNC_ATTR_NONNULL_ALL
 {
+  list_log(l, item, NULL, "append");
   if (l->lv_last == NULL) {
     // empty list
     l->lv_first = item;
@@ -521,7 +605,7 @@ list_T *tv_list_copy(const vimconv_T *const conv, list_T *const orig,
     return NULL;
   }
 
-  list_T *copy = tv_list_alloc();
+  list_T *copy = tv_list_alloc(tv_list_len(orig));
   tv_list_ref(copy);
   if (copyID != 0) {
     // Do this before adding the items, because one of the items may
@@ -741,6 +825,7 @@ void tv_list_reverse(list_T *const l)
   if (tv_list_len(l) <= 1) {
     return;
   }
+  list_log(l, NULL, NULL, "reverse");
 #define SWAP(a, b) \
   do { \
     tmp = a; \
@@ -779,6 +864,7 @@ void tv_list_item_sort(list_T *const l, ListSortItem *const ptrs,
   if (len <= 1) {
     return;
   }
+  list_log(l, NULL, NULL, "sort");
   int i = 0;
   TV_LIST_ITER(l, li, {
     ptrs[i].item = li;
@@ -867,6 +953,7 @@ listitem_T *tv_list_find(list_T *const l, int n)
   // Cache the used index.
   l->lv_idx = idx;
   l->lv_idx_item = item;
+  list_log(l, l->lv_idx_item, (void *)(uintptr_t)l->lv_idx, "find");
 
   return item;
 }
@@ -1817,12 +1904,16 @@ void tv_dict_set_keys_readonly(dict_T *const dict)
 /// Also sets reference count.
 ///
 /// @param[out]  ret_tv  Structure where list is saved.
+/// @param[in]  len  Expected number of items to be populated before list
+///                  becomes accessible from VimL. It is still valid to
+///                  underpopulate a list, value only controls how many elements
+///                  will be allocated in advance. @see ListLenSpecials.
 ///
 /// @return [allocated] pointer to the created list.
-list_T *tv_list_alloc_ret(typval_T *const ret_tv)
+list_T *tv_list_alloc_ret(typval_T *const ret_tv, const ptrdiff_t len)
   FUNC_ATTR_NONNULL_ALL
 {
-  list_T *const l = tv_list_alloc();
+  list_T *const l = tv_list_alloc(len);
   ret_tv->vval.v_list = l;
   ret_tv->v_type = VAR_LIST;
   ret_tv->v_lock = VAR_UNLOCKED;
diff --git a/src/nvim/eval/typval.h b/src/nvim/eval/typval.h
index c9a9a3e7e8..40a1738d9e 100644
--- a/src/nvim/eval/typval.h
+++ b/src/nvim/eval/typval.h
@@ -20,6 +20,9 @@
 #include "nvim/gettext.h"
 #include "nvim/message.h"
 #include "nvim/macros.h"
+#ifdef LOG_LIST_ACTIONS
+# include "nvim/memory.h"
+#endif
 
 /// Type used for VimL VAR_NUMBER values
 typedef int64_t varnumber_T;
@@ -31,6 +34,25 @@ typedef double float_T;
 /// Refcount for dict or list that should not be freed
 enum { DO_NOT_FREE_CNT = (INT_MAX / 2) };
 
+/// Additional values for tv_list_alloc() len argument
+enum {
+  /// List length is not known in advance
+  ///
+  /// To be used when there is neither a way to know how many elements will be
+  /// needed nor are any educated guesses.
+  kListLenUnknown = -1,
+  /// List length *should* be known, but is actually not
+  ///
+  /// All occurrences of this value should be eventually removed. This is for
+  /// the case when the only reason why list length is not known is that it
+  /// would be hard to code without refactoring, but refactoring is needed.
+  kListLenShouldKnow = -2,
+  /// List length may be known in advance, but it requires too much effort
+  ///
+  /// To be used when it looks impractical to determine list length.
+  kListLenMayKnow = -3,
+} ListLenSpecials;
+
 /// Maximal possible value of varnumber_T variable
 #define VARNUMBER_MAX INT64_MAX
 #define UVARNUMBER_MAX UINT64_MAX
@@ -304,6 +326,96 @@ typedef struct {
 
 typedef int (*ListSorter)(const void *, const void *);
 
+#ifdef LOG_LIST_ACTIONS
+
+/// List actions log entry
+typedef struct {
+  uintptr_t l;  ///< List log entry belongs to.
+  uintptr_t li1;  ///< First list item log entry belongs to, if applicable.
+  uintptr_t li2;  ///< Second list item log entry belongs to, if applicable.
+  int len;  ///< List length when log entry was created.
+  const char *action;  ///< Logged action.
+} ListLogEntry;
+
+typedef struct list_log ListLog;
+
+/// List actions log
+struct list_log {
+  ListLog *next;  ///< Next chunk or NULL.
+  size_t capacity;  ///< Number of entries in current chunk.
+  size_t size;  ///< Current chunk size.
+  ListLogEntry entries[];  ///< Actual log entries.
+};
+
+extern ListLog *list_log_first;  ///< First list log chunk, NULL if missing
+extern ListLog *list_log_last;  ///< Last list log chunk
+
+static inline ListLog *list_log_alloc(const size_t size)
+  REAL_FATTR_ALWAYS_INLINE REAL_FATTR_WARN_UNUSED_RESULT;
+
+/// Allocate a new log chunk and update globals
+///
+/// @param[in]  size  Number of entries in a new chunk.
+///
+/// @return [allocated] Newly allocated chunk.
+static inline ListLog *list_log_new(const size_t size)
+{
+  ListLog *ret = xmalloc(offsetof(ListLog, entries)
+                         + size * sizeof(ret->entries[0]));
+  ret->size = 0;
+  ret->capacity = size;
+  ret->next = NULL;
+  if (list_log_first == NULL) {
+    list_log_first = ret;
+  } else {
+    list_log_last->next = ret;
+  }
+  list_log_last = ret;
+  return ret;
+}
+
+static inline void list_log(const list_T *const l,
+                            const listitem_T *const li1,
+                            const listitem_T *const li2,
+                            const char *const action)
+  REAL_FATTR_ALWAYS_INLINE;
+
+/// Add new entry to log
+///
+/// If last chunk was filled it uses twice as much memory to allocate the next
+/// chunk.
+///
+/// @param[in]  l  List to which entry belongs.
+/// @param[in]  li1  List item 1.
+/// @param[in]  li2  List item 2, often used for integers and not list items.
+/// @param[in]  action  Logged action.
+static inline void list_log(const list_T *const l,
+                            const listitem_T *const li1,
+                            const listitem_T *const li2,
+                            const char *const action)
+{
+  ListLog *tgt;
+  if (list_log_first == NULL) {
+    tgt = list_log_new(128);
+  } else if (list_log_last->size == list_log_last->capacity) {
+    tgt = list_log_new(list_log_last->capacity * 2);
+  } else {
+    tgt = list_log_last;
+  }
+  tgt->entries[tgt->size++] = (ListLogEntry) {
+    .l = (uintptr_t)l,
+    .li1 = (uintptr_t)li1,
+    .li2 = (uintptr_t)li2,
+    .len = (l == NULL ? 0 : l->lv_len),
+    .action = action,
+  };
+}
+#else
+# define list_log(...)
+# define list_write_log(...)
+# define list_free_log()
+#endif
+
 // In a hashtab item "hi_key" points to "di_key" in a dictitem.
 // This avoids adding a pointer to the hashtab item.
 
@@ -377,6 +489,7 @@ static inline int tv_list_len(const list_T *const l)
 /// @param[in]  l  List to check.
 static inline int tv_list_len(const list_T *const l)
 {
+  list_log(l, NULL, NULL, "len");
   if (l == NULL) {
     return 0;
   }
@@ -460,8 +573,10 @@ static inline listitem_T *tv_list_first(const list_T *const l)
 static inline listitem_T *tv_list_first(const list_T *const l)
 {
   if (l == NULL) {
+    list_log(l, NULL, NULL, "first");
     return NULL;
   }
+  list_log(l, l->lv_first, NULL, "first");
   return l->lv_first;
 }
 
@@ -476,8 +591,10 @@ static inline listitem_T *tv_list_last(const list_T *const l)
 static inline listitem_T *tv_list_last(const list_T *const l)
 {
   if (l == NULL) {
+    list_log(l, NULL, NULL, "last");
     return NULL;
   }
+  list_log(l, l->lv_last, NULL, "last");
   return l->lv_last;
 }
 
@@ -545,6 +662,7 @@ extern bool tv_in_free_unref_items;
 #define _TV_LIST_ITER_MOD(modifier, l, li, code) \
     do { \
       modifier list_T *const l_ = (l); \
+      list_log(l_, NULL, NULL, "iter" #modifier); \
       if (l_ != NULL) { \
         for (modifier listitem_T *li = l_->lv_first; \
              li != NULL; li = li->li_next) { \