ref

1. https://nan01ab.github.io/2017/06/Amazon-Aurora.html 另外这个博客全是论文。不错
2. http://liuyangming.tech/05-2019/aurora.html博客不错 http://liuyangming.tech/02-2020/myrocks.html
3. https://www.cnblogs.com/cchust/p/7476876.html
4. http://mysql.taobao.org/monthly/2015/10/07/
5. https://zhuanlan.zhihu.com/p/27872160
6. https://blog.acolyer.org/2019/03/27/amazon-aurora-on-avoiding-distributed-consensus-for-i-os-commits-and-membership-changes/

原文链接

这段代码是研究 folly发现的 源代码在这里

前提: 方法

class Widget {
private:
  void forbidden();
};

访问

void hijack(Widget& w) {
  w.forbidden();  // ERROR!
}

  In function 'void hijack(Widget&)':
  error: 'void Widget::forbidden()' is private
  within this context
        |     w.forbidden();
        |   

解决思路

类函数可以通过指针来调用！

比如

class Calculator {
  float current_val = 0.f;
 public:
   void clear_value() { current_val = 0.f; };
   float value() const {
     return current_val;
   };

   void add(float x) { current_val += x; };
   void multiply(float x) { current_val *= x; };
};

using Operation = void (Calculator::*)(float);
Operation op1 = &Calculator::add;
Operation op2 = &Calculator::multiply;
Calculator calc{};
(calc.*op1)(123.0f); // Calls add
(calc.*op2)(10.0f);  // Calls multiply

私有的函数通过公有函数传指针，绕过

class Widget {
 public:
  static auto forbidden_fun() {
    return &Widget::forbidden;
  }
 private:
  void forbidden();
};

void hijack(Widget& w) {
  using ForbiddenFun = void (Widget::*)();
  ForbiddenFun const forbidden_fun = Widget::forbidden_fun();

  // Calls a private member function on the Widget
  // instance passed in to the function.
  (w.*forbidden_fun)();
}

但是一般函数是不会这么设计API的，太傻逼了，那怎么搞？

通过模版实例化绕过！

The C++17 standard contains the following paragraph (with the parts of interest to us marked in bold):

17.7.2 (item 12)

The usual access checking rules do not apply to names used to specify explicit instantiations. [Note: In particular, the template arguments and names used in the function declarator (including parameter types, return types and exception specifications) may be private types or objects which would normally not be accessible and the template may be a member template or member function which would not normally be accessible.]

重点 显式实例化

最终方案敲定： 私有成员函数指针做模版的非类型模版参数(NTTP)

// The first template parameter is the type
// signature of the pointer-to-member-function.
// The second template parameter is the pointer
// itself.
template <
  typename ForbiddenFun,
  ForbiddenFun forbidden_fun
>
struct HijackImpl {
  static void apply(Widget& w) {
    // Calls a private method of Widget
    (w.*forbidden_fun)();
  }
};

// Explicit instantiation is allowed to refer to
// `Widget::forbidden` in a scope where it's not
// normally permissible.
template struct HijackImpl<
  decltype(&Widget::forbidden),
  &Widget::forbidden
>;

void hijack(Widget& w) {
  HijackImpl<decltype(&Widget::forbidden), &Widget::forbidden>::apply(w);
}

但是还是报错，理论上可行，但实际上还是会提示私有，原因在于HijackImpl不是显式实例化

freind封装一层调用 + 显式实例化

// HijackImpl is the mechanism for injecting the
// private member function pointer into the
// hijack function.
template <
  typename ForbiddenFun,
  ForbiddenFun forbidden_fun
>
class HijackImpl {
  // Definition of free function inside the class
  // template to give it access to the
  // forbidden_fun template argument.
  // Marking hijack as a friend prevents it from
  // becoming a member function.
  friend void hijack(Widget& w) {
    (w.*forbidden_fun)();
  }
};
// Declaration in the enclosing namespace to make
// hijack available for name lookup.
void hijack(Widget& w);

// Explicit instantiation of HijackImpl template
// bypasses access controls in the Widget class.
template class
HijackImpl<
  decltype(&Widget::forbidden),
  &Widget::forbidden
>;

总结这几条

• 通过显式模版实例化把私有成员函数暴露出来
• 用成员函数的地址指针作为HijackImpl的模版参数
• 定义hijack函数在HijackImpl内部，直接用私有成员函数指针做函数调用
• 通过freind修饰来hijack，这样hijack就可以在外面调用里面的HijackImpl
• 显式实例化，这样调用就可以了

还有一个最终的问题，实现和实例化都在头文件，在所有的编译单元(translation units, TU)里, 显式实例化只能是一个，否则会报mutiple 链接错误，如何保证？

folly的做法，加个匿名tag，这样每个TU的符号名都不一样，最终方案如下

namespace {
// This is a *different* type in every translation
// unit because of the anonymous namespace.
struct TranslationUnitTag {};
}

void hijack(Widget& w);

template <
  typename Tag,
  typename ForbiddenFun,
  ForbiddenFun forbidden_fun
>
class HijackImpl {
  friend void hijack(Widget& w) {
    (w.*forbidden_fun)();
  }
};

// Every translation unit gets its own unique
// explicit instantiation because of the
// guaranteed-unique tag parameter.
template class HijackImpl<
  TranslationUnitTag,
  decltype(&Widget::forbidden),
  &Widget::forbidden
>;

参考

• The Power of Hidden Friends in C++’ posted 25 June 2019: https://www.justsoftwaresolutions.co.uk/cplusplus/hidden-friends.html
• Dan Saks ‘Making New Friends’ https://www.youtube.com/watch?v=POa_V15je8Y ](https://www.youtube.com/watch?v=POa_V15je8Y)
• Johannes Schaub ‘Access to private members. That’s easy!’,http://bloglitb.blogspot.com/2011/12/access-to-private-members-safer.html
• Johannes Schaub ‘Access to private members: Safer nastiness’, posted 30 December 2011: http://bloglitb.blogspot.com/2011/12/access-to-private-members-safer.html
• https://dfrib.github.io/a-foliage-of-folly/ 这个文章更进一步，接下来翻译这个

https://rigtorp.se/spinlock/

不多说，上代码

struct alignas(64) spinlock {
  std::atomic<bool> lock_ = {0};

  void lock() noexcept {
    for (;;) {
      // Optimistically assume the lock is free on the first try
      if (!lock_.exchange(true, std::memory_order_acquire)) {
        return;
      }
      // Wait for lock to be released without generating cache misses
      while (lock_.load(std::memory_order_relaxed)) {
        // Issue X86 PAUSE or ARM YIELD instruction to reduce contention between
        // hyper-threads
        __builtin_ia32_pause();
      }
    }
  }

  bool try_lock() noexcept {
    // First do a relaxed load to check if lock is free in order to prevent
    // unnecessary cache misses if someone does while(!try_lock())
    return !lock_.load(std::memory_order_relaxed) &&
           !lock_.exchange(true, std::memory_order_acquire);
  }

  void unlock() noexcept {
    lock_.store(false, std::memory_order_release);
  }
};

Ticket spinlocks

https://mfukar.github.io/2017/09/08/ticketspinlock.html

struct TicketSpinLock {
    /**
     * Attempt to grab the lock:
     * 1. Get a ticket number
     * 2. Wait for it
     */
    void enter() {
        const auto ticket = next_ticket.fetch_add(1, std::memory_order_relaxed);

        while (true) {
            const auto currently_serving = now_serving.load(std::memory_order_acquire);
            if (currently_serving == ticket) {
                break;
            }

            const size_t previous_ticket = ticket - currently_serving;
            const size_t delay_slots = BACKOFF_MIN * previous_ticket;

            while (delay_slots--) {
                spin_wait();
            }
        }
    }
    static inline void spin_wait(void) {
    #if (COMPILER == GCC || COMPILER == LLVM)
        /* volatile here prevents the asm block from being moved by the optimiser: */
        asm volatile("pause" ::: "memory");
    #elif (COMPILER == MVCC)
        __mm_pause();
    #endif
    }

    /**
     * Since we're in the critical section, no one can modify `now_serving`
     * but this thread. We just want the update to be atomic. Therefore we can use
     * a simple store instead of `now_serving.fetch_add()`:
     */
    void leave() {
        const auto successor = now_serving.load(std::memory_order_relaxed) + 1;
        now_serving.store(successor, std::memory_order_release);
    }

    /* These are aligned on a cache line boundary in order to avoid false sharing: */
    alignas(CACHELINE_SIZE) std::atomic_size_t now_serving = {0};
    alignas(CACHELINE_SIZE) std::atomic_size_t next_ticket = {0};
};

static_assert(sizeof(TicketSpinLock) == 2*CACHELINE_SIZE,
    "TicketSpinLock members may not be aligned on a cache-line boundary");

傻逼jenkins

不知道平台的人把jenkins怎么了，可能是升级了。能用内置CI还是不要用第三方组件，真是闹心

• 乱码

不止这一个命令，git rm都会乱码，我还以为是脚本隐藏了不可见字符，改了半天啊不好使

然后猜测是有中文注释的原因，去掉，依旧不行

最后发现参考链接1 在脚本前加一行

export LANG="en_US.UTF-8"  

• 找不到命令

PATH被清空了。在脚本前加上PATH定义即可

export PATH="/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin"

ref

1. https://blog.csdn.net/qq_35732831/article/details/85236562
2. https://www.cnblogs.com/weifeng1463/p/9419358.html
3. https://testerhome.com/topics/15136

ref

• https://www.mnstory.net/2017/07/10/network-tso-ufo-gso-lro-gro/
• https://www.mnstory.net/2017/07/05/network-ethernet-mtu-mss/
• https://github.com/moooofly/MarkSomethingDown/blob/master/Linux/TCP%20%E4%B9%8B%20TSO%20GSO%20LSO.md

asan常见的 抓错报告 编译带上 -fsanitize=address 链接带上 -lasan

global-buffer-overflow memcmp的长度可能越界

R: AddressSanitizer: global-buffer-overflow on address 0x000000a8f8ff at pc 0x7ff6eafde870 bp 0x7ffc75471220 sp 0x7ffc754709d0 READ of size 49 at 0x000000a8f8ff thread T0 #0 0x7ff6eafde86f in __interceptor_memcmp ../../../../gcc-5.4.0/libsanitizer/asan/asan_interceptors.cc:333

注意memcmp的第三个参数，取两个字符串中最小的长度

相关概念 OOB memory access

heap-buffer-overflow strlen访问内存越界

assert(n == strlen(val)); AddressSanitizer: heap-buffer-overflow

可能字符串没有分配’\0’的空间，用strlen会导致堆空间越界

AddressSanitizer: attempting to call malloc_usable_size

这个rocksdb的报错。 搜了一圈，二进制是jemalloc编的，和asan和rocksdb 有冲突产生的报错。临时禁止掉

ASAN_OPTIONS=check_malloc_usable_size=0

重编二进制，不带jemalloc，好使了

AddressSanitizer: attempting to call malloc_usable_size() for pointer which is not owned: 0x7f121aed6000
    #0 0x7f121f506990 in __interceptor_malloc_usable_size ../../../../gcc-5.4.0/libsanitizer/asan/asan_malloc_linux.cc:104
    #1 0x8c7929 in rocksdb::Arena::AllocateNewBlock(unsigned long) util/arena.cc:221
    #2 0x8c79c4 in rocksdb::Arena::AllocateFallback(unsigned long, bool) util/arena.cc:114
    #3 0x8df67a in rocksdb::LogBuffer::AddLogToBuffer(unsigned long, char const*, __va_list_tag*) util/log_buffer.cc:24
    #4 0x8df8c8 in rocksdb::LogToBuffer(rocksdb::LogBuffer*, char const*, ...) util/log_buffer.cc:88
    #5 0x749300 in rocksdb::DBImpl::FlushMemTableToOutputFile(rocksdb::ColumnFamilyData*, rocksdb::MutableCFOptions const&, bool*, rocksdb::JobContext*, rocksdb::SuperVersionContext*, rocksdb::LogBuffer*) db/db_impl_compaction_flush.cc:183
    #6 0x74c1f4 in rocksdb::DBImpl::FlushMemTablesToOutputFiles(rocksdb::autovector<rocksdb::DBImpl::BGFlushArg, 8ul> const&, bool*, rocksdb::JobContext*, rocksdb::LogBuffer*) db/db_impl_compaction_flush.cc:229
    #7 0x74d3b0 in rocksdb::DBImpl::BackgroundFlush(bool*, rocksdb::JobContext*, rocksdb::LogBuffer*, rocksdb::FlushReason*) db/db_impl_compaction_flush.cc:2025
    #8 0x74da4f in rocksdb::DBImpl::BackgroundCallFlush() db/db_impl_compaction_flush.cc:2059
    #9 0x8e8a27 in std::function<void ()>::operator()() const /usr/local/include/c++/5.4.0/functional:2267
    #10 0x8e8a27 in rocksdb::ThreadPoolImpl::Impl::BGThread(unsigned long) util/threadpool_imp.cc:265
    #11 0x8e8c0e in rocksdb::ThreadPoolImpl::Impl::BGThreadWrapper(void*) util/threadpool_imp.cc:303
    #12 0x7f121e1fb8ef in execute_native_thread_routine ../../../../../gcc-5.4.0/libstdc++-v3/src/c++11/thread.cc:84
    #13 0x7f121dd19dc4 in start_thread (/lib64/libpthread.so.0+0x7dc4)
    #14 0x7f121da477fc in __clone (/lib64/libc.so.6+0xf67fc)

AddressSanitizer can not describe address in more detail (wild memory access suspected).
SUMMARY: AddressSanitizer: bad-malloc_usable_size ../../../../gcc-5.4.0/libsanitizer/asan/asan_malloc_linux.cc:104 __interceptor_malloc_usable_size
Thread T2 created by T0 here:
    #0 0x7f121f4a80d4 in __interceptor_pthread_create ../../../../gcc-5.4.0/libsanitizer/asan/asan_interceptors.cc:179
    #1 0x7f121e1fba32 in __gthread_create /home/vdb/gcc-5.4-build/x86_64-unknown-linux-gnu/libstdc++-v3/include/x86_64-unknown-linux-gnu/bits/gthr-default.h:662
    #2 0x7f121e1fba32 in std::thread::_M_start_thread(std::shared_ptr<std::thread::_Impl_base>, void (*)()) ../../../../../gcc-5.4.0/libstdc++-v3/src/c++11/thread.cc:149

ref

• 这里有建议不要使用memcmp的讨论，还是怕越界 https://github.com/cesanta/mongoose/issues/564
• https://github.com/pcrain/slippc/issues/16 一个global buffer overflow case

fd数目有没有上涨？

 lsof -n|awk '{print $2}'| sort | uniq -c | sort -nr | head

20个最高fd线程

for x in `ps -eF| awk '{ print $2 }'`;do echo `ls /proc/$x/fd 2> /dev/null | wc -l` $x `cat /proc/$x/cmdline 2> /dev/null`;done | sort -n -r | head -n 20

具体到进程

ll /proc/pid/fd | wc -l

fd都用来干啥了

strace -p pid  -f -e read,write,close

Ref

• https://oroboro.com/file-handle-leaks-server/ 一个fd泄漏总结
  • 大众错误观点
    • time-wait太多导致fd占用 -> 不会。close就可以复用了。和time-wait两回事
    • close fd太慢 -> 不会。调用close返回值后就可以复用，是否真正关闭是系统的事儿
  • 几个常见场景
    • 子进程导致的重复fd
    • 太多连接
    • 创建子进程的时候关闭fd泄漏
• https://serverfault.com/questions/135742/how-to-track-down-a-file-descriptor-leak
• 查看所有tcphttp://blog.fatedier.com/2016/07/18/stat-all-connection-info-of-special-process-in-linux/

根据ppt和论文总结一下

概述

如今KV应用非常广泛，然而

• KV数据集在不同的应用上有不同的表现。对现实生活中的数据集分析非常有限
• 同一个应用，数据集也是不断变化的，怎么采集分析这些变动？
• 基于上，如何分析真正的瓶颈在哪，如何提高性能？

方法和工具

• 方法 收集数据集，分析数据结构，简历数据集模型，对比，提高benchmark性能，调优
• 工具 trace collector, trace replayer, trace analyzer, benchmarks

论文基于三个rocksdb应用来分析

案例分析

UDB

facebook做的社交数据收集工具，底层是mysql on myrocks

UDB的RocksDB通过6个ColumnFamily来存储不同类型的数据，分别是：

Object：存储object数据

Assoc：存储associations数据

Assoc_count：存储每个object的association数

Object_2ry，Assoc_2ry：object和association的secondary index

Non-SG：存储其他非社交图数据相关的服务

ZippyDB UP2X

rocksdb kv集群,用来保存AIML信息的

采集的数据类别

• 查询构成
• kv大小以及分布
• kv 热点以及访问分布
• qps
• 热key分布
• Key-space and temporal localities等等

由于上面的特性大多和业务相关，就不列举了。只列keysize

三个应用的 key size特点，都集中在一个范围 这不是废话吗

图太大不贴了，看ppt 15页

然后通过trace_replay重放数据集，自己构造一组类似的数据集，通过ycsb来模拟

具体怎么用的没有讲

ref

• 详细的论文描述看这里 https://www.jianshu.com/p/97d9bdd3cd4e 我只说了个大概
• https://www.usenix.org/system/files/fast20-cao_zhichao.pdf
• https://rockset.com/rocksdb/RocksDBZhichaoFAST2020.pdf?fbclid=IwAR0j6IpFrZ_hiYJOJLf5bMENUC2v86LUw69KWh_0ZBvQxMqWiDahyb0IYDw
• 文章中提到的工具在论文引用里介绍了，wiki 页面 https://github.com/facebook/rocksdb/wiki/RocksDB-Trace%2C-Replay%2C-Analyzer%2C-and-Workload-Generation 有机会可以试试

https://github.com/labuladong/fucking-algorithm

https://vjudge.net/article/187

https://github.com/youngyangyang04/leetcode-master

https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution

https://github.com/SharingSource/LogicStack-LeetCode/tree/main/LeetCode

思考

写在纸上

• 熟悉难度就去研究更难的。suffer
• 写纸上是个大纲，是更多的点子，在电脑上写有可能局限住，边想边写很容易遗漏

头脑风暴，想法和实现方法

• 有些时候会卡在思考上，想了半天，一行没写，没法破解成小问题
• 有时候想法对，但是后续的算法知识你不会，卡住了，或者没有足够的信息往下走了
• 有时候你后面的解决方法没问题，但想法本身是错误的。换个角度
• 问题的解决想法很多，可能你得挨个试试，拍个优先级
  • 比如求最小值？DP，贪心？最小割？分支界限法
  • 简单分析，重新尝试
• 哪怕是最垃圾的想法，也比没有想法要强，试一试呗

举例/抽象/具象

先用简单例子验证，然后归纳总结通项，然后分析各个元素之间的关系

限制

条件能够判定规模，限制大小

有些限制也可能是假的/误导人的。注意区别。限制条件是非常重要的

抽象题型，归纳成小问题

抽象题型，归纳通用场景

抽象题型，简化成子问题

一步一步来

抽象题型，转化成别的领域的问题

https://github.com/Strive-for-excellence/ACM-template

https://github.com/atcoder/ac-library

https://github.com/kth-competitive-programming/kactl/blob/master/content/graph/2sat.h

https://github.com/ouuan/Tree-Generator

https://github.com/BedirT/ACM-ICPC-Preparation/tree/master/Week01

https://github.com/hanzohasashi33/Competetive_programming

https://github.com/rachitiitr/DataStructures-Algorithms

https://csacademy.com/app/graph_editor/

经典题型

• Sliding window，滑动窗口类型
• two points, 双指针类型

• Fast & Slow pointers, 快慢指针类型

  • 龟兔赛跑

• Merge Intervals，区间合并类型

  • 重叠区间，判断交集
• Cyclic Sort，循环排序
• In-place Reversal of a LinkedList，链表翻转

• Tree Breadth First Search，树上的BFS

  • 用队列处理遍历
• Tree Depth First Search，树上的DFS
• 模拟堆栈
• Two Heaps，双堆类型 最大最小堆求中位数
• 优先队列
• 找一组数中的最大最小中位数
• Subsets，子集类型，一般都是使用多重DFS
• Modified Binary Search，改造过的二分
• Top ‘K’ Elements，前K个系列 堆
• K-way merge，多路归并

• DP

  • 0/1背包类型
  • Unbounded Knapsack，无限背包
  • 斐波那契数列
  • Palindromic Subsequence回文子系列
  • Longest Common Substring最长子字符串系列

• Topological Sort (Graph)，拓扑排序类型

  • hashmap邻接表

博弈问题 https://zhuanlan.zhihu.com/p/50787280

https://www.lintcode.com/ladder/47/

https://www.lintcode.com/ladder/2/

https://hrbust-acm-team.gitbooks.io/acm-book/content/chang_jian_ji_chu_cuo_wu.html

https://github.com/lightyears1998/polymorphism

https://github.com/menyf/acm-icpc-template

https://github.com/nataliekung/leetcode/tree/master/amazon

基础

• 完整详细的定义问题，找出解决问题所必须的基本抽象操作并定义一份API
• 间接地实现一种础计算法，给出一个开发用例并使用实际数据作为输入
• 当实现所能解决的问题的最大规模达不到期望时决定改进还是放弃
• 逐步改进，通过经验性分析和数学分析验证改进后的结果
• 用更高层侧的抽象表示数据接口活算法来设计更高级的改进版本
• 如果可能尽量为最坏情况下的性能提供保证，在处理普通数据时也要有良好的性能
• 在适当的时候讲更细致的深入援救留给有经验的研究之并继续解决下一个问题

排序

初级排序

• 选择排序
  • 运行时间和输入无关，并不能保留信息，有记忆信息更高效
• 插入排序
  • 如果有序，更友好
  • 进阶，希尔排序，分组插入排序
    • 分组怎么确定？

归并排序

• 难在原地归并
• 递归归并

快速排序

• 如何选位置？
• 改进方案
  • 小数组用插入排序
  • 三取样切分，中位数的选取

优先队列

二叉堆维护

• 插入
  • 加到数组末尾，上浮
• 删除最大元素
  • 最后一个元素放到顶端，下沉

多叉堆

堆排序

查找

基本抽象 符号表（dict） put/get/delete/contains

• 是否需要有序 min/max/range-find
• 插入和查找能不能都快
  • 插入块不考虑查找，链表，插入慢查找快，哈希表？
  • 二叉查找树，插入对数查找对数（二分）

二叉查找树

左边小右边大

删除节点

• 右边大，但是右边的左节点小，要找到右边没有左子节点的左节点，作为被删节点的交换节点
• 左边一定是小于右边的，所以要确定右边最小的，抬到被删节点的位置就行了
• 如果删除的是最小节点，那一定是左边的没有左子节点的节点，右子节点直接抬上来就行了，因为左边没了

最坏情况，数不平衡，退化成链表

范围查找 也就是中序遍历

平衡查找树

在插入场景下保证二叉查找树的完美平衡难度过大

• 2-3查找树，插入能尽可能的保持平衡

  • 如果插入终点是2节点，就转换成3节点
  • 如果终点是3节点
    • 只有一个3节点，该节点编程4节点，4节点可以轻松抽出二叉树子树
      • 父2节点，子3节点，同理，抽出子树，把子树父节点塞到父节点
      • 父3节点，子3节点，同理，抽出子树，把子树父节点塞到父节点，父节点再抽出子树，重复
      • 全是3节点 树高 +1

• 红黑二叉查找树描述2-3树？？

  • 替换3节点 抽出子树 左连接子树要标红 有图

  • 红连接放平，就是2-3树了

    

  一种等价定义

  • 红连接均为左连接
  • 没有任何一个节点同时和两条红连接相连
  • 完美黑色平衡，任意空连接到根节点的路径上的黑连接相同
• 旋转 就是单纯的改变方向

• 插入

  • 2节点插入
    • 单个2节点插入 一个元素就是单个2节点，左边就变红，如果右边 变红+旋转 最终都是3节点
    • 树底2节点插入，右边，那就旋转（交换位置）
  • 双键树插入，3节点插入 三种情况，小于/之间/大于
    • 大于，直接放到右边，平衡了，变黑
    • 小于，放到左边，两连红，旋转 变黑
    • 之间，放左边右子节点，旋转，在旋转，变黑
• 删除

• 红黑树性质

  • 高度
  • 到任意节点的路径平均长度

散列表

• 拉链法，也就是每个表项对应一个链表，有冲突就放到链表里
• 线性探测，放在下一个？？？长键簇会很多很难受

应用

• 查找表
• 索引，反向索引
• 稀疏矩阵 哈希表表达

图

无向图 边(edge) 顶点(vertex)

顶点名字不重要，用数字描述方便数组描述

特殊的图 自环 /平行边 含有平行边的叫 多重图 没有平行边/自环的是 简单图

两个顶点通过一条边相连 相邻 这条边 依附于这两个顶点

依附于顶点的边的总数称为顶点的 度数

子图 一幅图的所有变的一个子集以及所依附的顶点构成的图 许多问题要识别各种类型的子图

路径 由边顺序链接一系列顶点 u-v-w-x

简单路径 没有重复顶点的路径

环 至少包含一条边，起点终点相同的路径 u-v-w-x-u

简单环 不包含重复顶点和重复边的 环

如果从任意一个顶点都存在一条路径到达另一个顶点，我们称这幅图是 连通图

一幅非连通的图由若干连通部分组成，它们都是极大连通子图

` 无环图` 不包含环的图

树 无环连通图

生成树 连通图的子图，包含所有顶点，且是一棵树

森林 树的集合 生成树森林 生成树的集合

树的定义非常通用便于程序描述

图G 顶点V个

• G有V-1条边且不含环
• G有V-1条边且连通
• G连通，但删除任意一条编都会是它不在联通
• G是无环图，添加任意一条边会产生一条换
• G中任意一对顶点之间仅存在一条简单路径

图的 密度 已经连接的顶点对栈所有可能被连接的顶点对的比例 稀疏图 被连接的顶点对很少，稠密图 只有很少的抵抗点对之间没有边连接 如果一幅图中不同的边的数量在顶点总数的一个很小的常数倍之内就是稀疏的

二分图 能够将所所有节点分成两部分的图

图的表达方式

• 要求，空间，快
  • 邻接矩阵 V*V矩阵 空间太大
    • 平行边无法描述
  • 边的数组 查相邻不够快
  • 邻接表数组 顶点为索引的数组，数组内是和该顶点相邻的列表
    • 空间 V+E
• 遍历
  • DFS 其实也是dp数组方法的一种 递归要用堆栈
  • 连通性判定
• 寻找路径，路径最短判定？
  • BFS
• 连通分量？
• 间隔的度数？

有向图

有向图取反

有向图的可达性

• mark-sweep gc
• 有向图寻路
  • 单点有向路径
  • 单点最短有向路径

环/有向无环图(DAG)/有向图中的环

• 有向环检测,有向无环图就是不含有有向环的有向图
  • dfs
• 有向图中的强连通性
  • 构成有向环
  • 自反/对称/传递

最小生成树 MST

加权图 权值最小的生成树

• Prim/Kruskal
  • Prim 贪心 + 优先队列
• 几个简化
  • 权重不同，路径唯一
  • 只考虑连通
  • 权重可以是负数，意义不一定是距离
• 树的特点
  • 任意两个顶点都会产生一个新的环
  • 树删掉一条边就会得到两个独立的树
• 切分定理
  • 给定任意的切分，它的横切边中权重最小的必然是图的最小生成树 ？？
  • 这些算法都是一种贪心算法
    • V个顶点的任意加权连通图中属于最小生成树的边标记成黑色，初始为灰色，找到一种切分，横切边均不为黑色，将它权重最小的横切边标记为黑色，反复，直到标记了V-1条黑色边为止 ？？

动态规划

• 求最值的，通常要穷举，聪明的穷举(dp table)
• 重叠子问题以及最优子结构
  • 如果没有最优子结构，改造转换
• 正确的状态转移方程
  • 数学归纳
  • dp[i]代表了什么？
    • 最长上升子序列问题，dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度
  • 公式条件？
  • dp的遍历方向问题
    • 遍历的过程中，所需的状态必须是已经计算出来的。
    • 遍历的终点必须是存储结果的那个位置。

https://github.com/xtaci/algorithms

AFL是一种fuzz test工具，可以用来测试各种输入是否引起被测工具崩溃，比如gcc之类的。但是如果是网络模块，比如redis，nginx，没有好的模拟网络的办法。下面是一个演示示例，结合preeny来mock网络

准备工作

编译afl ，tarball在这里https://lcamtuf.coredump.cx/afl/下载

CC=/usr/local/bin/gcc make -j#注意自己的gcc版本。如果不需要考虑这个问题直接make
make install
#cmake指定，编译自己的二进制，指定g++
cmake ../ -DCXX_COMPILER_PATH=/usr/local/bin/afl-g++
#如果不是cmake，指定CC
CXX=/usr/local/bin/afl-g++ make -j

编译preeny没什么难的 参考https://github.com/zardus/preeny readme即可

测试

preeny可以把标准输入强制转换成socket输入，指定好LD_PRELOAD即可 参考链接 2 3 分别给了redis和nginx的例子

我这里使用的是redis，环境是wsl，参考的参考链接2生成的用例

LD_PRELOAD=/mnt/d/github/preeny/x86_64-linux-gnu/desock.so afl-fuzz -m 8G -i fuzz_in -o fuzz_out/ ./redis-server

测试preeny是否生效可以使用

LD_PRELOAD=/mnt/d/github/preeny/x86_64-linux-gnu/desock.so ./redis-server ./redis.conf  < set a b

跑了一个周末，没有发现崩溃的现象。

注意

wsl setsockopt TCP_NODELAY会报错invalid argument。屏蔽掉即可

ref

本文参考

1. 主要思路 https://copyninja.info/blog/afl-and-network-programs.html
2. https://volatileminds.net/2015/08/20/advanced-afl-usage-preeny.html
3. https://lolware.net/2015/04/28/nginx-fuzzing.html

几个afl使用例子

1. http://0x4c43.cn/2018/0722/use-afl-for-fuzz-testing/ 测试imageshark的
2. https://stfpeak.github.io/2017/06/11/Finding-bugs-using-AFL/ 举例测试输入漏洞
3. https://www.freebuf.com/articles/system/191536.html fuzz介绍，原理
4. http://zeroyu.xyz/2019/05/15/how-to-use-afl-fuzz/ afl使用指南
5. https://paper.seebug.org/496/ 原理
6. https://www.fastly.com/blog/how-fuzz-server-american-fuzzy-lop