<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Holmes He on Medium]]></title>
        <description><![CDATA[Stories by Holmes He on Medium]]></description>
        <link>https://medium.com/@holmeshe?source=rss-63f89bf0f9b4------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*d8Qc8oaS8um5JojmtdbcfA.png</url>
            <title>Stories by Holmes He on Medium</title>
            <link>https://medium.com/@holmeshe?source=rss-63f89bf0f9b4------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Fri, 20 Nov 2026 03:06:08 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@holmeshe/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Using React Native in Game Marketing Scenarios — Background]]></title>
            <link>https://medium.com/source-code/using-react-native-in-game-marketing-scenarios-background-493d735f6419?source=rss-63f89bf0f9b4------2</link>
            <guid isPermaLink="false">https://medium.com/p/493d735f6419</guid>
            <category><![CDATA[react]]></category>
            <category><![CDATA[game-development]]></category>
            <category><![CDATA[react-native]]></category>
            <dc:creator><![CDATA[Holmes He]]></dc:creator>
            <pubDate>Tue, 10 Jan 2023 21:48:19 GMT</pubDate>
            <atom:updated>2023-01-10T21:51:46.089Z</atom:updated>
            <content:encoded><![CDATA[<h3>Using React Native in Game Marketing Scenarios — Background</h3><p>Translated from: <a href="https://juejin.cn/post/7000628820814331918">https://juejin.cn/post/7000628820814331918</a></p><blockquote><em>In this context, “cross app” refers to the ability to share code and software modules across different executables on different platforms. It’s an advanced version of cross-platform development.</em></blockquote><p>Cross-app engineering has been evolving for several years. Popular frameworks such as mini-app, Flutter, and React Native, are all successful and mature frameworks. They are well-suited for different developers and are widely used in large-scale apps. The author has been fortunate to have been involved in the research and practice of these frameworks from an early stage and has designed and implemented a cross-app architecture that supports tens of millions of daily active users. The experiences and knowledge that have successfully increased development and product iteration efficiency are now being applied to the game industry.</p><p>React Native has become popular in recent times. It supports Android, iOS, and Windows, and it addresses the problem of cross-app development and hot reloading. One of its key features is its ability to release updates anytime, also known as OTA updates. When discussing React Native, it is often compared to Flutter, another popular solution. Both have their own advantages and disadvantages and there are many debates about which is better. However, it is important to keep in mind that the right tool should be selected based on the specific use case. In the following text, we will delve into how we use React Native for ads in games in more detail.</p><p>React Native is typically used for building apps and is adopted by big companies such as Facebook (Meta) and others. Weex, a similar framework, is also based on the principles of React Native. However, it is relatively rare to see React Native being used in game development. The main reason for this is that the mechanisms used in games and React Native are not well-suited to one another. Modern games are typically developed using frameworks such as Unity, Cocos, and UE4, which already support both Android and iOS and allow for OTA updates.</p><p>In native app development, fast iteration features are often achieved through the use of H5 (WebView) due to its ease of integration and development. Similarly, in the game industry, H5 pages are used for their multi-platform support, however they fall short in terms of responsive performance, fast loading times, and efficient memory usage — which are crucial factors in providing an immersive experience in games. To meet these requirements for fast iteration, quick releases, high performance, and immersion, the team conducted extensive A/B testing, and ultimately found React Native to be the optimal foundational infrastructure solution.</p><h3>Runtime Environment of Gaming</h3><p><strong>Rendering engine</strong>: In games, rendering engines are designed and implemented using the graphics library OpenGL. The native system UI is distinct from the UI in games, and is therefore not applicable. Additionally, the native system UI is not compatible with games because 1) the entire game runs as a single Activity on Android, and 2) the rendering engine provides customized animation attributes to enhance the immersive experience.</p><p><strong>Programming language</strong>: In game development, C# and Lua are commonly used languages. Unlike native Android and iOS development, games make use of native resources by using a bridge. The developer pool for games is relatively smaller compared to front-end and mobile developers. The UI of games is not directly shared with native, although there are solutions to enable UI sharing, e.g., <a href="https://www.cnblogs.com/zhxmdefj/p/13295243.html">sharing texture</a>, it’s not widely used in practice.</p><p><strong>Performance critical</strong>: Games have higher performance requirements for graphics and rendering compared to apps and demand more memory and CPU resources. This leads to stricter requirements for memory management and stability in hybrid pages.</p><p><strong>OTA</strong>: Games also commonly support OTA, such as Unity which supports JavaScript and Lua development. Often, activities and game logic are implemented with OTA for reduced package size and enhanced flexibility.</p><p><strong>Supported devices</strong>: Games, once developed, can run on different platforms, such as Android, iOS, PC and Android emulators, and these require higher compatibility than regular apps. For example, Android emulators support both x86 (32-bit and 64-bit) and arm (v7 and v8). However, for v7 and v8 which are commonly used on mobile phones, it requires instruction translation, which makes it more difficult for support.</p><h3>Selecting React Native</h3><p>Games commonly adopt H5 pages for its large amount of APIs and data analytics. However, H5 has inherent issues with memory and performance. Native UI cannot be used directly in games for the reasons mentioned before. In selecting a solution, compatibility with various native and game runtime environments is our primary concern.</p><ol><li>Games development often involves multiple platforms and inconsistent programming languages, requiring specific solutions like xLua and PureTS which adds maintenance burden.</li><li>Front-end/mobile solutions like H5 can address cross-app problems, but have poor performance and experience in game activities. React Native, open-sourced by Facebook, improves the cross-app experience, enhances performance and is leading the trend towards “greater front-end.” Similar frameworks, like Flutter with its embedded graphic engine and consistent UI, are being adopted by industry leaders. Another comparable framework, Week, also shares similar mechanism with React Native.</li></ol><p>Flutter or Weex are not selected as a solution, because Flutter is comparatively heavier than React Native and harder to integrate into existing projects CI/CD and IDE. It can also be challenging to separate game development and that of activity pages. Additionally, Weex’s weak ecosystem is not suitable for this use case. Other solutions like xLua+Unity and pureTS(open-sourced by Tencent), are also widely used. A comparison of these solutions can be found in the table below.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/5a97e973f5cd876d999e1da03310ac59/href">https://medium.com/media/5a97e973f5cd876d999e1da03310ac59/href</a></iframe><p>xLua and PureTS are great frameworks. We ultimately chose React Native as the best fit. However, React Native has limitations, such as not being able to layout the UI with the game as in xLua and PureTS which enlist in-game UI rendering. So we are also iterating on PureTS, but on a smaller scale:</p><ol><li>xLua and PureTS are game UI solutions that require a deep understanding of game design and architecture and are more suitable for game development teams.</li><li>These frameworks are designed for a certain game platform, not specific to all platforms, and require a large number of adaptations to support Cocos, Unity, UE4, etc. platforms, and higher maintenance costs.</li><li>It is hard to reuse native components, e.g., map, live streaming, etc.</li></ol><p>I understand you may have doubts about React Native’s limitations in rendering performance. However, we’ve chosen React Native and remain optimistic about its future despite some developers moving to Flutter or native development. We will further address your doubts by discussing the optimizations of the new architecture in future posts.</p><p><a href="https://reactnative.info/tags/bytedance/">bytedance</a>, <a href="https://reactnative.info/tags/translation/">translation</a></p><p><em>Originally published at </em><a href="https://reactnative.info/2023/01/02/using-react-native-for-in-game-ads-1/"><em>https://reactnative.info</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=493d735f6419" width="1" height="1" alt=""><hr><p><a href="https://medium.com/source-code/using-react-native-in-game-marketing-scenarios-background-493d735f6419">Using React Native in Game Marketing Scenarios — Background</a> was originally published in <a href="https://medium.com/source-code">source code</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[理解 Memcached 源码 — LRU II]]></title>
            <link>https://medium.com/source-code/%E7%90%86%E8%A7%A3-memcached-%E6%BA%90%E7%A0%81-lru-ii-3031914907ae?source=rss-63f89bf0f9b4------2</link>
            <guid isPermaLink="false">https://medium.com/p/3031914907ae</guid>
            <category><![CDATA[源码]]></category>
            <category><![CDATA[memcached]]></category>
            <category><![CDATA[哈希]]></category>
            <category><![CDATA[lru]]></category>
            <category><![CDATA[中文]]></category>
            <dc:creator><![CDATA[Holmes He]]></dc:creator>
            <pubDate>Mon, 28 Dec 2020 19:48:12 GMT</pubDate>
            <atom:updated>2020-12-28T19:48:12.300Z</atom:updated>
            <content:encoded><![CDATA[<h3>理解 Memcached 源码 — LRU II</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/700/1*gPHtYKKPsxshIOQIHfhmiw.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/photos/surQ2mkZNxw?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Brina Blum</a> on <a href="https://unsplash.com/search/photos/cake?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a></figcaption></figure><p>多半情况下，<strong>LRU</strong> 会和 <strong>哈希表</strong> 一起使用，然后我们把这个组合称为 <strong>LRU-cache</strong>。</p><p>在 <strong>LRU-cache</strong> 中, <strong>哈希表</strong> 提供快速索引的功能; 而 <strong>LRU</strong> 则是将 <strong>最近最少使用 （least recently used）</strong> 的元素在适当的时机标记为过期，并予以删除，用来防止缓存无限增大。本篇我们主要看 <strong>哈希表</strong> 的实现。</p><h3>概述 （课本都讲过了, <a href="https://holmeshe.me/cn/understanding-memcached-source-code-V/#%E6%A8%A1%E5%9D%97%E5%88%9D%E5%A7%8B%E5%8C%96">跳过</a>）</h3><p><strong>哈希表</strong> 本质上是一块 <em>固定大小</em> 的数组。数组的索引是由<em>键</em>被<em>哈希</em>生成的整形。在 <strong>哈希表</strong> 中，这个数组的元素也被称作 <strong>桶</strong>，以区别于 <strong>哈希表</strong> 本身的元素，<strong>item</strong>。当然，如果生成的索引超过 <strong>桶</strong> 的数量，则取模之。如果两个 <em>键值</em> 被 <em>哈希</em> 成同一个整形索引值，或者两个索引值被取模后的值刚好相同，则 <em>冲突</em> 发生。 所以一般做法是在每个 <strong>桶</strong> 上建立一个链表来存储所有 <em>冲突</em> 于此的键值对。</p><p>需要提一下，<em>冲突</em> 会降低 <strong>哈希表</strong> 的查找速度，原因很简单，因为要遍历链表 O(n)。处理方法也很简单，把数组大小扩容，然后重新对所有的元素进行 <em>重新哈希</em>，因为 <strong>桶</strong> 的数量增加了，<em>冲突</em> 也就减少了，而由 <em>冲突</em> 所形成的链表也就变少或变短了。 当然，<em>重新哈希</em> 的代价很大，所以一般是在性能实际下降时严重时才会发起。具体过程很<a href="https://holmeshe.me/cn/understanding-memcached-source-code-V/#%E6%89%A9%E5%AE%B9%E5%92%8C%E8%BF%81%E7%A7%BB">快会</a>就会讲到。</p><h3>模块初始化</h3><p>第一个方法</p><h3>hash_init</h3><p>用来确定 <em>哈希算法</em></p><pre>int hash_init(enum hashfunc_type type) {<br>    switch(type) {<br>        case JENKINS_HASH:<br>            hash = jenkins_hash;<br>            settings.hash_algorithm = &quot;jenkins&quot;;<br>            break;<br>        case MURMUR3_HASH:<br>            hash = MurmurHash3_x86_32;<br>            settings.hash_algorithm = &quot;murmur3&quot;;<br>            break;<br>        default:<br>            return -1;<br>    }<br>    return 0;<br>}</pre><pre>hash_init@hash.c</pre><p>这个方法在 <a href="https://holmeshe.me/cn/understanding-memcached-source-code-V/#">初始化过程中</a> 被调用。</p><p>其中参数 hash_type 被设置为 MURMUR3_HASH。这个是由命令行参数 <a href="https://holmeshe.me/cn/understanding-memcached-source-code-V/#">modern</a> 决定的。</p><p>第二个方法</p><h3>assoc_init</h3><p>为上述固定大小数组分配内存。</p><pre>void assoc_init(const int hashtable_init) {<br>    if (hashtable_init) {<br>        hashpower = hashtable_init;<br>    }<br>    primary_hashtable = calloc(hashsize(hashpower), sizeof(void *));<br>    if (! primary_hashtable) {<br>        fprintf(stderr, &quot;Failed to init hashtable.\n&quot;);<br>        exit(EXIT_FAILURE);<br>    }<br>...// scr: stat<br>}</pre><pre>hash_init@hash.c</pre><p>本方法也是在<a href="https://holmeshe.me/cn/understanding-memcached-source-code-V/#">初始化过程中</a>被调用</p><p>而初始大小则是由命令行参数<a href="https://holmeshe.me/cn/understanding-memcached-source-code-V/#">hashpower</a>确定。</p><p>如上所述，如果 <em>冲突</em> 过多而导致查询性能下降，我们需要用更大的数组来替换当前数组。接下来我们看一下这个过程</p><h3>扩容和迁移</h3><p>在 <strong>memcached</strong>, 这个扩容的阈值是 1.5, 即, 当 <strong>item</strong>（或者是 <strong>哈希表</strong> 元素） 的数量超过 <strong>桶</strong> 数量的 1.5 倍，上述机制会被激活。</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/443/0*65T6RuNA7oVXMvIB.png" /></figure><p>Expand hash map</p><pre>...<br>    if (! expanding &amp;&amp; hash_items &gt; (hashsize(hashpower) * 3) / 2) {<br>        assoc_start_expand();<br>    }<br>...</pre><pre>assoc_insert@assoc.c:173</pre><p>这里， assoc_start_expand 仅仅是设置了一个标志位 (i.e., do_run_maintenance_thread), 然后给辅助维护线程发信号并唤起之。然后由这个线程进行真正的扩容迁移工作。</p><pre>static void assoc_start_expand(void) {<br>    if (started_expanding)<br>        return;<br><br>    started_expanding = true;<br>    pthread_cond_signal(&amp;maintenance_cond);<br>}</pre><pre>assoc_insert@assoc.c:173</pre><h4>辅助维护线程主循环</h4><pre>static void *assoc_maintenance_thread(void *arg) {<br><br>  mutex_lock(&amp;maintenance_lock);<br>  while (do_run_maintenance_thread/* scr: the flag*/) {<br>    int ii = 0;<br><br>    /* There is only one expansion thread, so no need to global lock. */<br>    for (ii = 0; ii &lt; hash_bulk_move &amp;&amp; expanding; ++ii) { // scr: ----&gt; 2)<br>      item *it, *next;<br>      int bucket;<br>      void *item_lock = NULL;<br><br>      /* bucket = hv &amp; hashmask(hashpower) =&gt;the bucket of hash table<br>       * is the lowest N bits of the hv, and the bucket of item_locks is<br>       *  also the lowest M bits of hv, and N is greater than M.<br>       *  So we can process expanding with only one item_lock. cool! */<br>      if ((item_lock = item_trylock(expand_bucket))) { // scr: --------&gt; 3)<br>        for (it = old_hashtable[expand_bucket]; NULL != it; it = next) {<br>          next = it-&gt;h_next; // scr: ----------------------------------&gt; 4)<br>          bucket = hash(ITEM_key(it), it-&gt;nkey) &amp; hashmask(hashpower);<br>          it-&gt;h_next = primary_hashtable[bucket];<br>          primary_hashtable[bucket] = it;<br>        }<br><br>        old_hashtable[expand_bucket] = NULL; // scr: ----------------&gt; 4.1)<br><br>        expand_bucket++; // scr: --------------------------------------&gt; 5)<br>        if (expand_bucket == hashsize(hashpower - 1)) { // scr: -------&gt; 6)<br>          expanding = false;<br>          free(old_hashtable);<br>... // scr: ---------------------------------------------------&gt; stat &amp; log<br>        }<br>      } else {<br>        usleep(10*1000); // scr: ------------------------------------&gt; 3.1)<br>      }<br><br>      if (item_lock) { // scr: --------------------------------------&gt; 3.2)<br>        item_trylock_unlock(item_lock);<br>        item_lock = NULL;<br>      }<br>    }<br><br>    if (!expanding) {<br>      /* We are done expanding.. just wait for next invocation */<br>      started_expanding = false;<br>      pthread_cond_wait(&amp;maintenance_cond, &amp;maintenance_lock); // scr: &gt; 0)<br>      /* assoc_expand() swaps out the hash table entirely, so we need<br>       * all threads to not hold any references related to the hash<br>       * table while this happens.<br>       * This is instead of a more complex, possibly slower algorithm to<br>       * allow dynamic hash table expansion without causing significant<br>       * wait times.<br>       */<br>      pause_threads(PAUSE_ALL_THREADS);<br>      assoc_expand(); // scr: -----------------------------------------&gt; 1)<br>      pause_threads(RESUME_ALL_THREADS);<br>    }<br>  }<br>  return NULL;<br>}<br>assoc_maintenance_thread@assoc.c</pre><p>0) 从这里开始，线程被唤起并开始工作；而当整个工作完成后，或者根本就没有迁移的需要时，此线程也是在这里被挂起。</p><p>1) <a href="https://holmeshe.me/cn/understanding-memcached-source-code-V/#">assoc_expand</a> 为新的 <em>哈希表</em> 分配内存。这个新的 <em>哈希表</em> 后面会完全替换由<a href="https://holmeshe.me/cn/understanding-memcached-source-code-V/#assoc-init">初始化阶段</a>建立的既有 <em>哈希表</em>。</p><p>2) 一个批次仅迁移固定数量 （<a href="https://holmeshe.me/cn/understanding-memcached-source-code-V/#">hash_bulk_move</a>）的 <strong>item</strong>s。这样做的好处是在<a href="https://holmeshe.me/cn/understanding-memcached-source-code-V/#%E8%BE%85%E5%8A%A9%E7%BB%B4%E6%8A%A4%E7%BA%BF%E7%A8%8B%E7%BB%88%E6%AD%A2">stop_assoc_maintenance_thread</a>被调用时，辅助维护线程可以在完成当前批次立即停止，而不是要等到全量迁移完成。</p><p>3) (这里 “item lock” 实际上作用于 <strong>桶</strong> 上，所以<em>bucket lock</em>应该是个更合适的名字) 用 <a href="https://holmeshe.me/cn/understanding-memcached-source-code-V/#">item_trylock</a> (i.e., pthread_mutex_trylock) 来访问 <strong>桶</strong>; 3.1) 如果 <strong>桶</strong> 不可用，线程休眠10秒; 3.2) 当 <strong>桶</strong> 迁移完成时释放锁 （<a href="https://holmeshe.me/cn/understanding-memcached-source-code-V/#">item_trylock_unlock</a>）。</p><p>4) 对 <strong>bucket</strong> 上的所有 <strong>item</strong> 进行 <em>重新哈希</em>，并迁移至新 <strong>哈希表</strong>。</p><p>5) 继续对下一个 <strong>桶</strong> 进行迁移。</p><p>6) 所有的 <strong>桶</strong> 都迁移完成 -&gt; 回到 0)。</p><h4>辅助迁移线程启动</h4><pre>int start_assoc_maintenance_thread() {<br>    int ret;<br>    char *env = getenv(&quot;MEMCACHED_HASH_BULK_MOVE&quot;);<br>    if (env != NULL) {<br>        hash_bulk_move = atoi(env);<br>        if (hash_bulk_move == 0) {<br>            hash_bulk_move = DEFAULT_HASH_BULK_MOVE;<br>        }<br>    }<br>    pthread_mutex_init(&amp;maintenance_lock, NULL);<br>    if ((ret = pthread_create(&amp;maintenance_tid, NULL,<br>                              assoc_maintenance_thread, NULL)) != 0) {<br>        fprintf(stderr, &quot;Can&#39;t create thread: %s\n&quot;, strerror(ret));<br>        return -1;<br>    }<br>    return 0;<br>}</pre><pre>start_assoc_maintenance_thread@assoc.c</pre><p>和<a href="https://holmeshe.me/cn/understanding-memcached-source-code-V/#Module-initialization">其他的初始化方法</a>类似，这个方法也是在<a href="https://holmeshe.me/cn/understanding-memcached-source-code-V/#">系统初始化</a>时调用的。</p><h4>辅助维护线程终止</h4><p>stop_assoc_maintenance_thread 是在<a href="https://holmeshe.me/cn/understanding-memcached-source-code-V/#">系统终止</a>时被调用的。语义上来看本方法对应的是 start_assoc_maintenance_thread，而功能上看，则和 assoc_start_expand 里的操作正好相反。</p><pre>void stop_assoc_maintenance_thread() {<br>    mutex_lock(&amp;maintenance_lock);<br>    do_run_maintenance_thread = 0;<br>    pthread_cond_signal(&amp;maintenance_cond);<br>    mutex_unlock(&amp;maintenance_lock);<br><br>    /* Wait for the maintenance thread to stop */<br>    pthread_join(maintenance_tid, NULL);<br>}</pre><pre>stop_assoc_maintenance_thread@assoc.c</pre><p>如上述，扩容和迁移的状态对所有的 <strong>哈希表</strong> 相关操作都有影响。下面我们具体看看有哪些影响。</p><h3>CRUD</h3><h4>assoc_insert</h4><pre>int assoc_insert(item *it, const uint32_t hv) {<br>    unsigned int oldbucket;<br><br>    if (expanding &amp;&amp;<br>        (oldbucket = (hv &amp; hashmask(hashpower - 1))) &gt;= expand_bucket)<br>    {<br>        it-&gt;h_next = old_hashtable[oldbucket]; // scr: -------------------&gt; 1)<br>        old_hashtable[oldbucket] = it;<br>    } else {<br>        it-&gt;h_next = primary_hashtable[hv &amp; hashmask(hashpower)]; // scr: &gt; 2)<br>        primary_hashtable[hv &amp; hashmask(hashpower)] = it;<br>    }<br><br>    pthread_mutex_lock(&amp;hash_items_counter_lock);<br>    hash_items++; // scr: ------------------------------------------------&gt; 3)<br>    if (! expanding &amp;&amp; hash_items &gt; (hashsize(hashpower) * 3) / 2) {<br>        assoc_start_expand();<br>    }<br>    pthread_mutex_unlock(&amp;hash_items_counter_lock);<br><br>    MEMCACHED_ASSOC_INSERT(ITEM_key(it), it-&gt;nkey, hash_items);<br>    return 1;<br>}</pre><pre>assoc_insert@assoc.c</pre><p>1) 如果正在扩容中，并且指定<em>键</em>对应的 <strong>桶</strong> 还没有被迁移，则将 <strong>item</strong> 插入至 old_hashtable。这里注意我们是用老的 <strong>桶</strong> 数（i.e., hashmask(hashpower - 1))）来计算下标。</p><p>2) 如果不满足以上情况, 将 <strong>item</strong> 插入 primary_hashtable。</p><p>3) 增加全局计数 <a href="https://holmeshe.me/cn/understanding-memcached-source-code-V/#">hash_items</a> （即<strong>item</strong> 数）。 如果 hash_items 超过了阈值， 则启动上文描述的扩容过程。</p><h4>assoc_find</h4><pre>item *assoc_find(const char *key, const size_t nkey, const uint32_t hv) {<br>    item *it;<br>    unsigned int oldbucket;<br><br>    if (expanding &amp;&amp;<br>        (oldbucket = (hv &amp; hashmask(hashpower - 1))) &gt;= expand_bucket)<br>    {<br>        it = old_hashtable[oldbucket]; // scr: ---------------------------&gt; 1)<br>    } else {<br>        it = primary_hashtable[hv &amp; hashmask(hashpower)]; // scr: --------&gt; 2)<br>    }<br><br>    item *ret = NULL;<br>    int depth = 0;<br>    while (it) { // scr: -------------------------------------------------&gt; 3)<br>        if ((nkey == it-&gt;nkey) &amp;&amp; (memcmp(key, ITEM_key(it), nkey) == 0)) {<br>            ret = it;<br>            break;<br>        }<br>        it = it-&gt;h_next;<br>        ++depth;<br>    }<br>    MEMCACHED_ASSOC_FIND(key, nkey, depth);<br>    return ret;<br>}</pre><pre>assoc_find@assoc.c</pre><p>1) 和<a href="https://holmeshe.me/cn/understanding-memcached-source-code-V/#assoc-insert">assoc_insert</a>类似，这步用于定位尚未被<em>重新哈希</em>的<em>键</em>。并从 old_hashtable 取出对应的 <strong>桶</strong>。</p><p>2) 同样，如果没有进行扩容或者已经完成迁移，则从 primary_hashtable 中取。</p><p>3) 遍历<em>链表</em>并找到<em>键</em>对应的 <strong>item</strong>。这个也是标准操作了。</p><h4>assoc_delete</h4><p>基于<a href="https://holmeshe.me/understanding-memcached-source-code-IV/#assoc-delete-remove-from-hash-map">上篇</a>的讲解，当考虑到扩容迁移时，这里唯一需要重新讨论的函数是 _hashitem_before。和<a href="https://holmeshe.me/cn/understanding-memcached-source-code-V/#assoc_find">assoc_find</a>类似，这里的变化仅仅是，当对应的<em>键</em>尚未完成迁移时从old_hashtable读取。</p><pre>static item** _hashitem_before (const char *key, const size_t nkey, const uint32_t hv) {<br>    item **pos;<br>    unsigned int oldbucket;<br><br>    if (expanding &amp;&amp;<br>        (oldbucket = (hv &amp; hashmask(hashpower - 1))) &gt;= expand_bucket)<br>    {<br>        pos = &amp;old_hashtable[oldbucket]; // scr: ---------------------------&gt; diff)<br>    } else {<br>        pos = &amp;primary_hashtable[hv &amp; hashmask(hashpower)];<br>    }<br><br>    while (*pos &amp;&amp; ((nkey != (*pos)-&gt;nkey) || memcmp(key, ITEM_key(*pos), nkey))) {<br>        pos = &amp;(*pos)-&gt;h_next;<br>    }<br>    return pos;<br>}</pre><pre>_hashitem_before@assoc.c<br></pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3031914907ae" width="1" height="1" alt=""><hr><p><a href="https://medium.com/source-code/%E7%90%86%E8%A7%A3-memcached-%E6%BA%90%E7%A0%81-lru-ii-3031914907ae">理解 Memcached 源码 — LRU II</a> was originally published in <a href="https://medium.com/source-code">source code</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Understanding The Memcached Source Code-Event Driven III]]></title>
            <link>https://medium.com/source-code/understanding-the-memcached-source-code-event-driven-iii-8641b97f165d?source=rss-63f89bf0f9b4------2</link>
            <guid isPermaLink="false">https://medium.com/p/8641b97f165d</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[open-source]]></category>
            <category><![CDATA[memcached]]></category>
            <category><![CDATA[source-code]]></category>
            <category><![CDATA[event-driven-systems]]></category>
            <dc:creator><![CDATA[Holmes He]]></dc:creator>
            <pubDate>Sun, 02 Jun 2019 10:30:00 GMT</pubDate>
            <atom:updated>2019-06-05T12:12:39.617Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*o_O0ApPNNettQvxa9hPESA.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/@matthew_t_rader?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Matthew T Rader</a> on <a href="https://unsplash.com/search/photos/cake?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a></figcaption></figure><blockquote>Slab allocator is the core module of the cache system, which largely determines how efficient the bottleneck resource, memory, can be utilised. The other 3 parts, namely, LRU algorithm for entry expiration; and an event driven model based on libevent; and the consistent harsh for data distribution, are built around it.</blockquote><p><a href="https://medium.com/source-code/understanding-the-memcached-source-code-slab-i-9199de613762">Slab I</a><br><a href="https://medium.com/source-code/understanding-the-memcached-source-code-slab-ii-6477c0482548">Slab II</a><br><a href="https://medium.com/source-code/https-medium-com-source-code-understanding-the-memcached-source-code-slab-iii-cb06e577d73e">Slab III</a><br><a href="https://medium.com/source-code/understanding-the-memcached-source-code-lru-i-8b383c561638">LRU I</a><br><a href="https://medium.com/source-code/understanding-the-memcached-source-code-lru-ii-ea4067863652">LRU II</a><br><a href="https://medium.com/source-code/understanding-the-memcached-source-code-lru-iii-87d1c7497cb9">LRU III</a><br><a href="https://medium.com/source-code/understanding-the-memcached-source-code-event-driven-i-cd6c947c4092">Event driven I</a><br><a href="https://medium.com/source-code/understanding-the-memcached-source-code-event-driven-ii-8d6249d62943">Event driven II</a><br>Event driven III (this article)</p><p>We continue examining the other two operations, i.e., create and delete, in the <strong>event-driven</strong> context. Now it’s a good chance to revisit the <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#Core-data-structure-conn">core data structure</a> and look at the</p><h3>Properties in discussion</h3><p>wbuf - the address for <em>write buffer</em> for simple response output (e.g., STORED). used by <a href="https://holmeshe.me/understanding-memcached-source-code-IX/#out-string">out_string</a></p><p>wcurr - not very useful as it points to the same address as wbuf. used by <a href="https://holmeshe.me/understanding-memcached-source-code-IX/#conn-write">conn_write</a></p><p>wsize - the total size of <em>write buffer</em>. used by <a href="https://holmeshe.me/understanding-memcached-source-code-IX/#out-string">out_string</a> to determine buff overflow</p><p>wbytes - the length of data populated in <em>write buffer</em>. value is set in <a href="https://holmeshe.me/understanding-memcached-source-code-IX/#out-string">out_string</a>; used by <a href="https://holmeshe.me/understanding-memcached-source-code-IX/#conn-write">conn_write</a> when writing it to the &quot;real&quot; output buffer <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#add-iov">iov</a></p><p>write_and_go - set to conn_new_cmd in the <a href="https://holmeshe.me/understanding-memcached-source-code-IX/#out-string">very last step</a> to form a &quot;state loop&quot;</p><p>ritem - one of the essential properties for <a href="https://holmeshe.me/understanding-memcached-source-code-IX/#conn-nread">data reading</a>. it is set to the address of the data portion of the actual <strong>item</strong> created by <a href="https://holmeshe.me/understanding-memcached-source-code-IX/#process-update-command">create command</a></p><p>rlbytes - one of the essential properties for <a href="https://holmeshe.me/understanding-memcached-source-code-IX/#conn-nread">data reading</a>. it is set to the length of the data in need</p><p>item - record of the actual <strong>item</strong> created by <a href="https://holmeshe.me/understanding-memcached-source-code-IX/#process-update-command">create command</a></p><p>noreply - determined by the command. we assume it is set to false</p><h3>Create</h3><p>As usual, we start with a command sent to a <strong>Memcached</strong> server.</p><pre>&gt; add test 0 60 11 (\r\n)<br>&gt; hello world</pre><p>As mentioned in <a href="https://holmeshe.me/understanding-memcached-source-code-VI/#Create">LRU III</a>, two passes are involved in the command processing, the first pass creates an empty object after reading the first line, and the second populates the object with the concrete value contained in the second line. Such division is for the multiple <em>I/O</em> triggered by line breaks in <em>telnet</em>.</p><blockquote>In fact, most of the logic involved in this post has been discussed before such as in <a href="https://holmeshe.me/understanding-memcached-source-code-VI">LRU III</a> and <a href="https://holmeshe.me/understanding-memcached-source-code-VIII">Event Driven II</a>. Hence this post will only resolve the missing parts and linking points.</blockquote><p>For the first command,</p><pre>&gt; add test 0 60 11 (\r\n)</pre><p>The <strong>Memcached</strong> instance outputs the following lines. This time we omit the output for accepting the new connection</p><pre>27: going from conn_new_cmd to conn_waiting<br>27: going from conn_waiting to conn_read<br>27: going from conn_read to conn_parse_cmd<br>27: Client using the ascii protocol<br>&lt;27 add test 0 60 11<br>27: going from conn_parse_cmd to conn_nread</pre><p>The logic for command reading and parsing ( conn_new_cmd to conn_parse_cmd) are the same as what described in <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#conn-new-cmd">Event Driven II</a>. The difference is that</p><h4>process_update_command</h4><p>is invoked after the command parsing. Though the method has been examined in <a href="https://holmeshe.me/understanding-memcached-source-code-VI/#process-update-command">LRU III</a>, it is worth reminding that the last step is to update the <em>session context</em> for the next <strong>state</strong> ( conn_nread) which handles the actual data reading.</p><pre>static void process_update_command(conn *c, token_t *tokens, const size_t ntokens, int comm, bool handle_cas) {<br>... // LRU III<br>    c-&gt;item = it;<br>    c-&gt;ritem = ITEM_data(it);<br>    c-&gt;rlbytes = it-&gt;nbytes;<br>    c-&gt;cmd = comm;<br>    conn_set_state(c, conn_nread);<br>}</pre><p>Next we look at the second command</p><pre>...<br>&gt; hello world</pre><p>and its associated output</p><pre>&gt; NOT FOUND test<br>&gt;27 STORED<br>27: going from conn_nread to conn_write<br>27: going from conn_write to conn_new_cmd<br>...</pre><p>The key code fragment for the <strong>state</strong> switching above is</p><h4>conn_nread</h4><pre>...<br>static void drive_machine(conn *c) {<br>...<br>        case conn_nread:<br>            if (c-&gt;rlbytes == 0) { // scr: ---------------------&gt; 5)<br>                complete_nread(c);<br>                break;<br>            }<br><br>...// scr: error handling<br><br>            /* first check if we have leftovers in the conn_read buffer */<br>            if (c-&gt;rbytes &gt; 0) { // scr: -----------------------&gt; 1)<br>                int tocopy = c-&gt;rbytes &gt; c-&gt;rlbytes ? c-&gt;rlbytes : c-&gt;rbytes;<br>                if (c-&gt;ritem != c-&gt;rcurr) {<br>                    memmove(c-&gt;ritem, c-&gt;rcurr, tocopy);<br>                }<br>                c-&gt;ritem += tocopy;<br>                c-&gt;rlbytes -= tocopy;<br>                c-&gt;rcurr += tocopy;<br>                c-&gt;rbytes -= tocopy;<br>                if (c-&gt;rlbytes == 0) {<br>                    break;<br>                }<br>            }<br><br>            /*  now try reading from the socket */<br>            res = read(c-&gt;sfd, c-&gt;ritem, c-&gt;rlbytes); // scr: --&gt; 2)<br>            if (res &gt; 0) {<br>...// scr: stat<br>                if (c-&gt;rcurr == c-&gt;ritem) {<br>                    c-&gt;rcurr += res;<br>                }<br>                c-&gt;ritem += res;<br>                c-&gt;rlbytes -= res;<br>                break;<br>            }<br>            if (res == 0) { /* end of stream */ // scr: --------&gt; 3)<br>                conn_set_state(c, conn_closing);<br>                break;<br>            } // scr: ------------------------------------------&gt; 4)<br>            if (res == -1 &amp;&amp; (errno == EAGAIN || errno == EWOULDBLOCK)) {<br>                if (!update_event(c, EV_READ | EV_PERSIST)) {<br>...// scr: error handling<br>                }<br>                stop = true;<br>                break;<br>            }<br>...// scr: error handling<br>            break;<br>...</pre><p>1) Check if there are some leftover data (from the <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#try-read-network">command read</a> phase). If so, read directly.</p><blockquote>More specific, say, if you can enter the command above fast enough (maybe copy paste it directly to <em>telnet</em>), the data portion will be coalesced in with the command by <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#try-read-network">read</a>.</blockquote><p>2) Read the data to the memory pointed by ritem.</p><p>3) If the connection is closed ( <em>FIN</em>) in the middle of the read, close the session.</p><p>4) If the data is separated into multiple reads, then set the <em>drive machine</em> to listen to more data and suspend.</p><p>5) Normal termination — read finished, call <a href="https://holmeshe.me/understanding-memcached-source-code-VI/#complete-nread-ascii">complete_nread</a> which is covered in <a href="https://holmeshe.me/understanding-memcached-source-code-VI">LRU III</a>.</p><p>The missing part in <a href="https://holmeshe.me/understanding-memcached-source-code-VI">LRU III</a> is out_string. Combined with conn_write, it functions as a simpler version of <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#process-get-command">process_get_command</a> for &quot;simple response&quot;, and the actual data writing is handled by <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#conn-mwrite">conn_mwrite</a> (note the fall through... in the switch case) block which, as discussed, changes the <strong>state</strong> back to conn_new_cmd. Next we discuss the process in detail.</p><h4>out_string</h4><pre>static void out_string(conn *c, const char *str) {<br>    size_t len;<br>    <br>...//scr: not applicable<br>    <br>    if (settings.verbose &gt; 1)<br>        fprintf(stderr, &quot;&gt;%d %s\n&quot;, c-&gt;sfd, str);<br>        <br>    /* Nuke a partial output... */<br>    c-&gt;msgcurr = 0; // scr: ---------------------------&gt; 1)<br>    c-&gt;msgused = 0;<br>    c-&gt;iovused = 0;<br>    add_msghdr(c);<br>    <br>    len = strlen(str); // scr: ------------------------&gt; 2)<br>    if ((len + 2) &gt; c-&gt;wsize) {<br>        /* ought to be always enough. just fail for simplicity */<br>        str = &quot;SERVER_ERROR output line too long&quot;;<br>        len = strlen(str);<br>    }   <br>    <br>    memcpy(c-&gt;wbuf, str, len); // scr: ----------------&gt; 3)<br>    memcpy(c-&gt;wbuf + len, &quot;\r\n&quot;, 2);<br>    c-&gt;wbytes = len + 2;<br>    c-&gt;wcurr = c-&gt;wbuf;<br>    <br>    conn_set_state(c, conn_write); // scr: ------------&gt; 4)<br>    c-&gt;write_and_go = conn_new_cmd; // scr: -----------&gt; 5)<br>    return;<br>}</pre><p>1) Initialize the iov. the mechanism and <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#add-msghdr">add_msghdr</a> has been discussed in the <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/">last post</a></p><p>2) Calculate string length, and be paranoid for survival.</p><p>3) Populate wbuf with the output string and point wcurr to wbuf.</p><p>4) Indicate the next <strong>state</strong> conn_write.</p><p>5) Set the last <strong>state</strong> to conn_new_cmd and form the &quot;loop&quot;.</p><h4>conn_write</h4><pre>...<br>        case conn_write:<br>            /*<br>             * We want to write out a simple response. If we haven&#39;t already,<br>             * assemble it into a msgbuf list (this will be a single-entry<br>             * list for TCP or a two-entry list for UDP).<br>             */<br>            if (c-&gt;iovused == 0 || (IS_UDP(c-&gt;transport) &amp;&amp; c-&gt;iovused == 1)) {<br>                if (add_iov(c, c-&gt;wcurr, c-&gt;wbytes) != 0) { //scr&gt;1)<br>                    if (settings.verbose &gt; 0)<br>                        fprintf(stderr, &quot;Couldn&#39;t build response\n&quot;);<br>                    conn_set_state(c, conn_closing);<br>                    break;<br>                }<br>            }<br><br>            /* fall through... */<br>        case conn_mwrite:<br>...// scr: discussed<br>            switch (transmit(c)) {<br>            case TRANSMIT_COMPLETE:<br>                if (c-&gt;state == conn_mwrite) {<br>...// scr: discussed<br>                } else if (c-&gt;state == conn_write) {<br>                    if (c-&gt;write_and_free) {<br>...// scr: not applicable<br>                    }<br>                    conn_set_state(c, c-&gt;write_and_go); // scr: &gt; 2)<br>                } else {<br>...// scr: discussed<br>                }<br>                break;<br>...</pre><p>1) Add the content of “write buffer” to the actual iov.</p><p>2) Pick up the write_and_go (i.e., conn_new_cmd) and set it to the next <strong>state</strong>.</p><p>Next, we send the</p><h3>Delete</h3><p>command to delete the entry we just added.</p><pre>&gt; delete test</pre><p>And the output this time is</p><pre>28: going from conn_read to conn_parse_cmd<br>&lt;28 delete test<br>&gt; FOUND KEY test<br>&gt;28 DELETED<br>28: going from conn_parse_cmd to conn_write<br>28: going from conn_write to conn_new_cmd<br>28: going from conn_new_cmd to conn_waiting<br>28: going from conn_waiting to conn_read</pre><p>Like <a href="https://holmeshe.me/understanding-memcached-source-code-IX/#create">add</a> the entry point of this command (after parsed) is <a href="https://holmeshe.me/understanding-memcached-source-code-VI/#process-delete-command">process_delete_command</a> which has been fully covered in <a href="https://holmeshe.me/understanding-memcached-source-code-VI">LRU III</a>. Furthermore, out_string is called within process_delete_command to trigger the <strong>state</strong> switches from conn_write, and back to conn_new_cmd.</p><h3>To go</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*ywRQJaxGb9ak2Xxp.png" /></figure><p><em>Originally published at </em><a href="https://holmeshe.me/understanding-memcached-source-code-IX/"><em>https://holmeshe.me</em></a><em> on June 2, 2019.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=8641b97f165d" width="1" height="1" alt=""><hr><p><a href="https://medium.com/source-code/understanding-the-memcached-source-code-event-driven-iii-8641b97f165d">Understanding The Memcached Source Code-Event Driven III</a> was originally published in <a href="https://medium.com/source-code">source code</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[理解 Memcached — LRU I]]></title>
            <link>https://medium.com/source-code/%E7%90%86%E8%A7%A3-memcached-%E6%BA%90%E7%A0%81-33289f4fc437?source=rss-63f89bf0f9b4------2</link>
            <guid isPermaLink="false">https://medium.com/p/33289f4fc437</guid>
            <category><![CDATA[中文]]></category>
            <category><![CDATA[open-source]]></category>
            <category><![CDATA[cache]]></category>
            <category><![CDATA[lru-cache]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Holmes He]]></dc:creator>
            <pubDate>Sat, 18 May 2019 10:28:00 GMT</pubDate>
            <atom:updated>2019-06-01T23:59:26.201Z</atom:updated>
            <cc:license>https://creativecommons.org/licenses/by-nd/4.0/</cc:license>
            <content:encoded><![CDATA[<h3>理解 Memcached 源码 — LRU I</h3><figure><img alt="" src="https://cdn-images-1.medium.com/proxy/1*r2kFpDPNuqxxi4caokcJtg.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/photos/jCWpF3uteec?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Anita Austvika</a> on <a href="https://unsplash.com/search/photos/cake?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a></figcaption></figure><p>多半情况下， <strong>LRU</strong> 会和 哈希表一起使用，然后我们把这个组合称为</p><h3>LRU 缓存</h3><p>在 <strong>LRU缓存</strong> 中，哈希表提供了快速随机访问对象的能力；而 <strong>LRU</strong>（算法）则用于淘汰 <strong>很久没用</strong> ( <strong>least recently used</strong>) 的对象，来避免缓存无限增加。我们先大致看下 <strong>LRU</strong> 组成。</p><h4>链表</h4><p>从技术上来说， <strong>LRU</strong> 算法是在链表上完成的 — 当一个表项被使用（访问或更新）， <strong>LRU</strong> 会先做移除，然后把它重新插入到表头。这样，越接近表尾的对象就是 <strong>越久没使用</strong> ( <strong>least recently used</strong>)，淘汰起来比较简单。</p><h4>哈希表</h4><p>链表是不支持快速的随机访问的，所以需要和 <strong>哈希表</strong> 一起使用。之前我们之前已经读过， <strong>板</strong> 子系统的空闲列表是通过链表把 <strong>板</strong> 里的 <strong>块</strong> (chuck) 串起来形成的。在 <strong>LRU缓存</strong> 里也差不多，而这次用链表串起来的是表项。大致看起来是这样：</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/410/0*kqjtzyA46sshMl3n.png" /></figure><p>从另外一个维度看起来可能会更直观一点：</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/429/0*CcAn0cHE0fvfygj1.png" /></figure><h3>核心数据结构 — item</h3><pre>typedef struct _stritem {<br>    /* Protected by LRU locks */<br>    struct _stritem *next;<br>    struct _stritem *prev;<br>    /* Rest are protected by an item lock */<br>    struct _stritem *h_next;    /* hash chain next */<br>    rel_time_t      time;       /* least recent access */<br>    rel_time_t      exptime;    /* expire time */<br>    int             nbytes;     /* size of data */<br>    unsigned short  refcount;<br>    uint8_t         nsuffix;    /* length of flags-and-length string */<br>    uint8_t         it_flags;   /* ITEM_* above */<br>    uint8_t         slabs_clsid;/* which slab class we&#39;re in */<br>    uint8_t         nkey;       /* key length, w/terminating null and padding */<br>    /* this odd type prevents type-punning issues when we do<br>     * the little shuffle to save space when not using CAS. */<br>    union {<br>... // scr: cas<br>        char end; // scr: flexible array member indicating the item header &quot;end&quot;<br>    } data[];<br>    /* if it_flags &amp; ITEM_CAS we have 8 bytes CAS */<br>    /* then null-terminated key */<br>    /* then &quot; flags length\r\n&quot; (no terminating null) */<br>    /* then data with terminating \r\n (no terminating null; it&#39;s binary!) */<br>} item;</pre><h4>使用到的字段</h4><p>next, prev - <strong>LRU 链表</strong> 指针, 在 <a href="https://holmeshe.me/understanding-memcached-source-code-VI/#do-item-alloc">do_item_alloc (LRU III)</a> 初始化, 被 <a href="https://holmeshe.me/cn/understanding-memcached-source-code-IV/#item-link-q-add-to-linked-list">item_link_q</a>, <a href="https://holmeshe.me/cn/understanding-memcached-source-code-IV/#item-unlink-q-remove-from-linked-list">item_unlink_q</a> 使用。</p><p>h_next - <em>hash 冲突链表</em> 的指针, 在 <a href="https://holmeshe.me/understanding-memcached-source-code-VI/#do-item-alloc">do_item_alloc (LRU III)</a> 初始化, 被 <a href="https://holmeshe.me/cn/understanding-memcached-source-code-IV/#assoc-insert-add-to-hash-map">assoc_insert</a>, <a href="https://holmeshe.me/cn/understanding-memcached-source-code-IV/#assoc-delete-remove-from-hash-map">assoc_delete</a>, <a href="https://holmeshe.me/understanding-memcached-source-code-II">多个模块 (LRU II)</a> 使用。</p><p>time - 最后访问时间, 在 <a href="https://holmeshe.me/cn/understanding-memcached-source-code-IV/#do-item-link">do_item_link</a> 中设置, 被 <a href="https://holmeshe.me/understanding-memcached-source-code-VI/#lru-pull-tail">lru_pull_tail (LRU III)</a> 使用。</p><p>exptime - 超时时间（由请求参数指定）, 在 <a href="https://holmeshe.me/understanding-memcached-source-code-VI/#do-item-alloc">do_item_alloc (LRU III)</a> 初始化, 被 <a href="https://holmeshe.me/understanding-memcached-source-code-VI/#lru-pull-tail">lru_pull_tail (LRU III)</a> 使用。</p><p>nbytes - 数据大小（由请求参数指定），在 <a href="https://holmeshe.me/understanding-memcached-source-code-VI/#do-item-alloc">do_item_alloc (LRU III)</a> 初始化。</p><p>refcount - 引用计数, 在 <a href="https://holmeshe.me/understanding-memcached-source-code-III/#do-slabs-alloc">do_slabs_alloc (Slab III)</a> 初始化, 被 <a href="https://holmeshe.me/cn/understanding-memcached-source-code-IV/#do-item-link">do_item_link</a> 使用。</p><p>nsuffix - 在 <a href="https://holmeshe.me/understanding-memcached-source-code-VI/#do-item-alloc">do_item_alloc (LRU III)</a> 用 item_make_header 初始化。</p><p>it_flags - 在 <a href="https://holmeshe.me/understanding-memcached-source-code-VI/#do-item-alloc">do_item_alloc (LRU III)</a> 初始化, 被 <a href="https://holmeshe.me/cn/understanding-memcached-source-code-IV/#do-item-link">do_item_link</a>, <a href="https://holmeshe.me/cn/understanding-memcached-source-code-IV/#do-item-unlink">do_item_unlink</a> 使用。</p><p>slabs_clsid - 当前对象存在的具体的 <strong>LRU 链表</strong> , 被 <a href="https://holmeshe.me/understanding-memcached-source-code-VI/#do-item-alloc">do_item_alloc (LRU III)</a> 初始化, 在 <a href="https://holmeshe.me/cn/understanding-memcached-source-code-IV/#item-link-q-add-to-linked-list">item_link_q</a>, <a href="https://holmeshe.me/cn/understanding-memcached-source-code-IV/#item-unlink-q-remove-from-linked-list">item_unlink_q</a> 使用。</p><p>nkey - 键大小, 在 <a href="https://holmeshe.me/understanding-memcached-source-code-VI/#do-item-alloc">do_item_alloc (LRU III)</a> 中计算, 被 <a href="https://holmeshe.me/cn/understanding-memcached-source-code-IV/#assoc-delete-remove-from-hash-map">assoc_delete</a> 使用。</p><h4>块的内存布局</h4><p>我们在 <a href="https://holmeshe.me/understanding-memcached-source-code-II/#do-slabs-free">do_slabs_free</a> 提到过 <strong>块</strong> 。这次我们直接通过数据结构来看下它的构造。</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*R7HqOWSdA02aP46d.png" /></figure><p>下面我们来读直接操作 <strong>LRU</strong> 的相关代码。</p><h3>do_item_link</h3><pre>int do_item_link(item *it, const uint32_t hv) { // scr: -------&gt; 1)<br>...<br>    it-&gt;it_flags |= ITEM_LINKED;                // scr: -------&gt; 2)<br>    it-&gt;time = current_time;<br><br>... // scr: stat<br><br>    /* Allocate a new CAS ID on link. */<br>... // scr: cas<br>    assoc_insert(it, hv);                       // scr: -------&gt; 3)<br>    item_link_q(it);                            // scr: -------&gt; 4)<br>    refcount_incr(&amp;it-&gt;refcount);               // scr: -------&gt; 5)<br>... // scr: stat<br><br>    return 1;<br>}</pre><p>1) 正常理解， hv 应该就是哈希值 &quot;hashed value&quot; 的缩写。</p><p>2) 设置 it-&gt;it_flags 的 ITEM_LINKED 标志, 然后将当前时间赋值给 it-&gt;time 。</p><p>3) 将 <strong>对象</strong> 添加到哈系表。</p><p>4) 将 <strong>对象</strong> 添加到链表。</p><p>5) 递增 <em>reference count</em> 。</p><p>要注意 <em>引用计数</em> 代表了有几个子模块同时在使用该资源。这个字段是决定是否回收该资源的关键参考 （在这里， <strong>对象</strong> 同时被 <strong>板</strong> 和 <strong>LRU</strong> 在使用）。我在 <a href="https://holmeshe.me/cpp-pointers/">另一篇文章</a> 里详细讨论了C++里相似的机制。</p><h4>item_link_q — 添加至链表</h4><p><a href="https://holmeshe.me/cn/understanding-memcached-source-code-IV/">item_link_q</a> 是主力函数 do_item_link_q 的线程安全的简单包装。</p><pre>static void do_item_link_q(item *it) { /* item is the new head */<br>    item **head, **tail;<br>    assert((it-&gt;it_flags &amp; ITEM_SLABBED) == 0);<br><br>    head = &amp;heads[it-&gt;slabs_clsid];           // scr: -----&gt; 1)<br>    tail = &amp;tails[it-&gt;slabs_clsid];<br>    assert(it != *head);<br>    assert((*head &amp;&amp; *tail) || (*head == 0 &amp;&amp; *tail == 0));<br>    it-&gt;prev = 0;                             // scr: -----&gt; 2)<br>    it-&gt;next = *head;<br>    if (it-&gt;next) it-&gt;next-&gt;prev = it;<br>    *head = it;<br>    if (*tail == 0) *tail = it;<br>    sizes[it-&gt;slabs_clsid]++;                 // scr: -----&gt; 3)<br>    return;<br>}</pre><p>1) 从对应的 <strong>LRU 链表</strong> （由 slabs_clsid指定）获取 head 和 tail。注意 slabs_clsid 是用队列类型加过盐的，所以每个 <strong>板组</strong> 可能会包含复数个列表。</p><p>2) 标准动作，”添加表头项”。</p><p>3) 增加全局的数组 大小 。</p><h4>assoc_insert — 添加至哈希表</h4><pre>int assoc_insert(item *it, const uint32_t hv) { // scr: again, hv -&gt; hash value<br>    unsigned int oldbucket;<br><br>... // scr: expanding related operations<br>    } else {<br>        it-&gt;h_next = primary_hashtable[hv &amp; hashmask(hashpower)]; // scr:  1)<br>        primary_hashtable[hv &amp; hashmask(hashpower)] = it;         // scr:  2)<br>    }<br><br>... // scr: expanding related operations<br>}</pre><p>1) 冲突处理。没冲突？将 h_next 直接设置为 null 。</p><p>2) 将 <strong>对象</strong> 添加到 <a href="https://holmeshe.me/cn/understanding-memcached-source-code-IV/">primary_hashtable</a> 的桶。</p><p>扩容的逻辑先留个坑， <a href="https://holmeshe.me/understanding-memcached-source-code-V/#Scale-up-amp-entry-migration">下篇</a> 再来讲。</p><h3>do_item_unlink</h3><pre>void do_item_unlink(item *it, const uint32_t hv) {<br>    MEMCACHED_ITEM_UNLINK(ITEM_key(it), it-&gt;nkey, it-&gt;nbytes);<br>    if ((it-&gt;it_flags &amp; ITEM_LINKED) != 0) {<br>        it-&gt;it_flags &amp;= ~ITEM_LINKED;         // scr: ---------&gt; 1)<br>... // scr: stat<br>        assoc_delete(ITEM_key(it), it-&gt;nkey, hv); // scr: -----&gt; 2)<br>        item_unlink_q(it);                    // scr: ---------&gt; 3)<br>        do_item_remove(it);                   // scr: ---------&gt; *)<br>    }<br>}</pre><ol><li>清除 it-&gt;it_flags 的 ITEM_LINKED 位。</li></ol><p>2) 从哈希表移除 <strong>对象</strong> 。</p><p>3) 从链表移除 <strong>对象</strong> 。</p><p>*) 实际释放 <strong>对象</strong> 的逻辑后面会讲。</p><h4>item_unlink_q — 从链表移除</h4><p>同上， <a href="https://holmeshe.me/cn/understanding-memcached-source-code-IV/">item_unlink_q</a> 只是一个对于实调函数 do_item_unlink_q 线程安全的简单封装。</p><pre>static void do_item_unlink_q(item *it) {<br>    item **head, **tail;<br>    head = &amp;heads[it-&gt;slabs_clsid];           // scr: ---------&gt; 1)<br>    tail = &amp;tails[it-&gt;slabs_clsid];<br><br>    if (*head == it) {                        // scr: ---------&gt; 2)<br>        assert(it-&gt;prev == 0);<br>        *head = it-&gt;next;<br>    }<br>    if (*tail == it) {<br>        assert(it-&gt;next == 0);<br>        *tail = it-&gt;prev;<br>    }<br>    assert(it-&gt;next != it);<br>    assert(it-&gt;prev != it);<br><br>    if (it-&gt;next) it-&gt;next-&gt;prev = it-&gt;prev;<br>    if (it-&gt;prev) it-&gt;prev-&gt;next = it-&gt;next;<br>    sizes[it-&gt;slabs_clsid]--;                 // scr: ---------&gt; 3)<br>    return;<br>}</pre><p>1) 同样, 获取 由 slabs_clsid 指定的 <strong>LUR 链表</strong> 的 head 和 tail。</p><p>2) 标准的 “移除链表项” 操作。</p><p>3) 减少全局的数组大小 。</p><h4>assoc_delete — 从哈希表移除</h4><pre>static item** _hashitem_before (const char *key, const size_t nkey, const uint32_t hv) {<br>    item **pos;<br>    unsigned int oldbucket;<br><br>... // scr: expanding related operations<br>    } else {<br>        pos = &amp;primary_hashtable[hv &amp; hashmask(hashpower)]; // scr1)<br>    }<br><br>    while (*pos &amp;&amp; ((nkey != (*pos)-&gt;nkey) || memcmp(key, ITEM_key(*pos), nkey))) {<br>        pos = &amp;(*pos)-&gt;h_next; // scr: -------------------------&gt; 2)<br>    }<br>    return pos;<br>}<br><br>...<br><br>void assoc_delete(const char *key, const size_t nkey, const uint32_t hv) {<br>    item **before = _hashitem_before(key, nkey, hv);<br><br>    if (*before) {<br>        item *nxt;<br>...<br>        nxt = (*before)-&gt;h_next; // scr: -----------------------&gt; 3)<br>        (*before)-&gt;h_next = 0;   /* probably pointless, but whatever. */<br>        *before = nxt; // scr: ---------------------------------&gt; 4)<br>        return;<br>    }<br>    /* Note:  we never actually get here.  the callers don&#39;t delete things<br>       they can&#39;t find. */<br>    assert(*before != 0);<br>}</pre><p>1) 通过 hv 获取桶。</p><p>2) 遍历冲突链表并比较 key。注意这里的返回值是 <strong>指定元素上一个元素的 </strong><strong>next 字段的地址</strong>。而当没有冲突时，这个地址就是桶本身。</p><p>3) 将找到的下一个元素赋值给 nxt。</p><p>4) 更新 <strong>指定元素上一个元素的 </strong><strong>next 字段</strong>。</p><h3>打包带走</h3><p>试下<a href="https://leetcode.com/problems/lru-cache/">这个</a></p><p><em>Originally published at </em><a href="https://holmeshe.me/cn/understanding-memcached-source-code-IV/"><em>https://holmeshe.me</em></a><em> on May 18, 2019.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=33289f4fc437" width="1" height="1" alt=""><hr><p><a href="https://medium.com/source-code/%E7%90%86%E8%A7%A3-memcached-%E6%BA%90%E7%A0%81-33289f4fc437">理解 Memcached — LRU I</a> was originally published in <a href="https://medium.com/source-code">source code</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[理解 Memcached — Slab III]]></title>
            <link>https://medium.com/source-code/%E7%90%86%E8%A7%A3-memcached-slab-iii-e73d1f5dec39?source=rss-63f89bf0f9b4------2</link>
            <guid isPermaLink="false">https://medium.com/p/e73d1f5dec39</guid>
            <category><![CDATA[open-source]]></category>
            <category><![CDATA[cache]]></category>
            <category><![CDATA[memory-management]]></category>
            <category><![CDATA[中文]]></category>
            <dc:creator><![CDATA[Holmes He]]></dc:creator>
            <pubDate>Sun, 24 Mar 2019 05:36:57 GMT</pubDate>
            <atom:updated>2019-06-01T23:59:10.595Z</atom:updated>
            <content:encoded><![CDATA[<h3>理解 Memcached源码 — Slab III</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/1*rWrmg9I8AcLQF1YElbw_BQ.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/photos/s4RaGIo2eYI?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Sharon McCutcheon</a> on <a href="https://unsplash.com/search/photos/cake?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a></figcaption></figure><p>上次我们看完了内存分配，以及形成待分配列表（<em>free list</em>，即slots）的过程。本篇我们继续查看如何使用建立好的数据结构来分配/回收块内存，并将它们用于存储<strong>对象</strong>。</p><p>首先，我们来看</p><h3>do_slabs_alloc</h3><p>这个函数对应讨论过的<a href="https://holmeshe.me/cn/understanding-memcached-source-code-II/#do-slabs-free">do_slabs_free</a>.</p><p>这里do_slabs_alloc的“公有”接口是slabs_alloc。slabs_alloc除了提供了对外接口外，还对核心数据结构加了线程锁以保证此函数（在<strong>Memcached</strong>被配置为多线程时，multithreaded）线程安全。</p><pre>static void *do_slabs_alloc(const size_t size, unsigned int id, unsigned int *total_chunks,<br>        unsigned int flags) {<br>    slabclass_t *p;<br>    void *ret = NULL;<br>    item *it = NULL;<br>...<br>    p = &amp;slabclass[id]; // scr: -------------------------------&gt; 1)<br>...<br>    if (total_chunks != NULL) {<br>        *total_chunks = p-&gt;slabs * p-&gt;perslab; // scr: --------&gt; 2)<br>    }<br>    /* fail unless we have space at the end of a recently allocated page,<br>       we have something on our freelist, or we could allocate a new page */<br>    if (p-&gt;sl_curr == 0 &amp;&amp; flags != SLABS_ALLOC_NO_NEWPAGE) { // scr: --&gt; *)<br>        do_slabs_newslab(id); // scr: -------------------------&gt; 3)<br>    }<br><br>    if (p-&gt;sl_curr != 0) {<br>        /* return off our freelist */<br>        it = (item *)p-&gt;slots; // scr: ------------------------&gt; 4)<br>        p-&gt;slots = it-&gt;next;<br>        if (it-&gt;next) it-&gt;next-&gt;prev = 0;<br>        /* Kill flag and initialize refcount here for lock safety in slab<br>         * mover&#39;s freeness detection. */<br>        it-&gt;it_flags &amp;= ~ITEM_SLABBED; // scr: ----------------&gt; 5)<br>        it-&gt;refcount = 1;<br>        p-&gt;sl_curr--;<br>        ret = (void *)it; // scr: -----------------------------&gt; 6)<br>    } else {<br>        ret = NULL;<br>    }<br><br>...<br>    return ret;<br>}</pre><p>1）id代表 <strong>Slab组</strong>。之前提到过，不同大小的对象会用不同的 <strong>Slab组</strong> 来存储。换句话说，id 的值由<em>对象大小</em>决定。这个过程后面会讨论。</p><p>2）total_chunks 是出参，用于存储当前Slab组的空闲<em>内存块</em>（<em>memory chunk</em>），或者说是待分配列表里还有多少空位。if (total_chunks != NULL) 则说明这个是可选参数。</p><p>*）和字面意思一样，SLABS_ALLOC_NO_NEWPAGE（flags）即使在没有空闲内存块时也不会额外分配新的 <strong>Slab</strong> 来满足后续分配需要。这个选项并不属于<em>对象分配</em>的通常路径，所以暂时忽略。</p><p>3）没有空闲内存块时分配新 <strong>Slab</strong>。这里很容易看到p-&gt;sl_curr 表示空闲<em>内存块</em>的数量。这个变量的值会在每次调用这个函数时递减（看第5步）。</p><p>另一方面, 这个字段在<a href="https://holmeshe.me/cn/understanding-memcached-source-code-II/#do-slabs-free">do_slabs_free</a>里自增。 注意 <em>new slab</em> 在<a href="https://holmeshe.me/cn/understanding-memcached-source-code-II/#New-slab">这篇</a>也提到过。</p><p>4）从待分配列表（<em>free list</em>，即<em>slots</em>）表头干掉一个元素（<strong>f</strong>），并将其赋值给it。</p><p>在<a href="https://holmeshe.me/cn/understanding-memcached-source-code-II/#do-slabs-free">do_slabs_free</a>, 内存块也是从表头加入的。</p><p>5) 清除对应<em>内存块</em>(<strong>f</strong>)的ITEM_SLABBED标志，将引用次数设置为1，并且内存块的数量p-&gt;sl_curr 减少1。</p><p>同样，这个标志在<a href="https://holmeshe.me/cn/understanding-memcached-source-code-II/#do-slabs-free">do_slabs_free</a>中被设置。</p><p>6) 返回(<strong>f</strong>).</p><p>下面我们来看如何通过对象大小来决定id，对应的函数是</p><h3>slabs_clsid</h3><pre>unsigned int slabs_clsid(const size_t size) {<br>    int res = POWER_SMALLEST;<br><br>    if (size == 0)<br>        return 0;<br>    while (size &gt; slabclass[res].size)<br>        if (res++ == power_largest)     /* won&#39;t fit in the biggest slab */<br>            return 0;<br>    return res;<br>}</pre><p>slabs_clsid 主要由一个 while 循环组成，这个循环会渐次找到最小的Slab组来刚好达到申请对象的大小要求。这个函数是在 do_item_alloc 中先于 slabs_alloc 被调用。 我们会在后面的文章中讨论 do_item_alloc。</p><p><em>Originally published at </em><a href="https://holmeshe.me/cn/understanding-memcached-source-code-III/"><em>holmeshe.me</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e73d1f5dec39" width="1" height="1" alt=""><hr><p><a href="https://medium.com/source-code/%E7%90%86%E8%A7%A3-memcached-slab-iii-e73d1f5dec39">理解 Memcached — Slab III</a> was originally published in <a href="https://medium.com/source-code">source code</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[理解 Memcached — Slab II]]></title>
            <link>https://medium.com/source-code/%E7%90%86%E8%A7%A3-memcached-slab-ii-e24e4074ef89?source=rss-63f89bf0f9b4------2</link>
            <guid isPermaLink="false">https://medium.com/p/e24e4074ef89</guid>
            <category><![CDATA[open-source]]></category>
            <category><![CDATA[中文]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[memory-management]]></category>
            <category><![CDATA[cache]]></category>
            <dc:creator><![CDATA[Holmes He]]></dc:creator>
            <pubDate>Sun, 24 Mar 2019 05:28:52 GMT</pubDate>
            <atom:updated>2019-06-01T23:58:49.221Z</atom:updated>
            <content:encoded><![CDATA[<h3>理解 Memcached 源码— Slab II</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/1*vi8Mp1y0fHZbhbgB2VVo6A.jpeg" /></figure><p>这次我们继续看用于 <strong>Slab</strong> 的内存是如何分配的。</p><p>首先我们继续看 slabs_init 的两个实参。第一个是 settings.maxbytes — 控制这个 <strong>Memcached</strong> 实例可以使用的总内存大小。在传入 slabs_init 之前，这个参数被赋值为全局变量 mem_limit。</p><p>另外一个怎是 preallocate。它决定了是否为（各个）<strong>Slab组</strong> 预分配 内存。这个参数的值由 L 命令行参数来决定。</p><p>下面我们来看 slabs 的内存分配函数。</p><h3>New slab</h3><p>具体来说，这个函数用于给 <strong>Slab组</strong> 分配大小为1M的内存块（<strong>slab</strong>）。而 <strong>Slab组</strong> 由参数 id 指定。</p><pre>static int do_slabs_newslab(const unsigned int id) {<br>    slabclass_t *p = &amp;slabclass[id]; // scr: ------------------&gt; 1)<br>    slabclass_t *g = &amp;slabclass[SLAB_GLOBAL_PAGE_POOL]; // scr:&gt; *)<br>    int len = settings.slab_reassign ? settings.item_size_max // scr: ---&gt; 2)<br>        : p-&gt;size * p-&gt;perslab;<br>    char *ptr;<br><br>    if ((mem_limit &amp;&amp; mem_malloced + len &gt; mem_limit &amp;&amp; p-&gt;slabs &gt; 0 // -&gt; 3)<br>         &amp;&amp; g-&gt;slabs == 0)) {<br>        mem_limit_reached = true;<br>        MEMCACHED_SLABS_SLABCLASS_ALLOCATE_FAILED(id);<br>        return 0;<br>    }<br><br>    if ((grow_slab_list(id) == 0) || // scr: -----------------&gt; 4)<br>        (((ptr = get_page_from_global_pool()) == NULL) &amp;&amp; // -&gt; *)<br>        ((ptr = memory_allocate((size_t)len)) == 0))) { //scr:&gt; 5)<br><br>        MEMCACHED_SLABS_SLABCLASS_ALLOCATE_FAILED(id);<br>        return 0;<br>    }<br><br>    memset(ptr, 0, (size_t)len);<br>    split_slab_page_into_freelist(ptr, id); // scr: ----------&gt; 6)<br><br>    p-&gt;slab_list[p-&gt;slabs++] = ptr; // scr: ------------------&gt; 7)<br>    MEMCACHED_SLABS_SLABCLASS_ALLOCATE(id);<br><br>    return 1;<br>}</pre><p>1）slabclass[id] 是 <strong>Slab组</strong> 的数据结构。<a href="https://holmeshe.me/cn/understanding-memcached-source-code-I/#Module-initialization">上篇</a>讨论了这个数组的初始化。</p><p>2）settings.slab_reassign 决定是否启用 再平衡 策略。如果启用，未使用的 slabs 不会被立即释放，而是分配给其他 <strong>Slab组</strong> 使用，这就产生了一个问题，即所有 <strong>Slab组</strong> 都需要使用统一大小的 <strong>slab</strong>。所以这个设置同时也决定了是否使用 <em>同种slab</em> （大小为 settings.item_size_max，或者上述的1M），还是 <em>异种slab</em> （p-&gt;size * p-&gt;perslab）。除了用命令行参数 &quot;slab_reassign&quot; 以外，&quot;modern&quot; 也会设置这个值，而本文也会用1M作为 <strong>slab</strong> 的大小。</p><p>N.b. *, <em>rebalancing mechanism</em> will be discussed later when we have a better understanding of the LRU module.</p><p>3）检查内存使用是否超出上线。</p><p>4）grow_slab_list 检查是否增长 slabclass_t.slab_list，如果需要，则增长之。</p><p>5）memory_allocate 是真正分配 <strong>slab</strong> 内存的函数。如上述，这里的 len 是1M。</p><p>6）split_slab_page_into_freelist 初始化 （或者是 free）刚刚分配的 <strong>slab</strong> 内存用作对象存储。这个函数会在下一节讨论。</p><p>7) 将刚刚分配的 <strong>slab</strong> 加入到 slabclass_t.slab_list.</p><p>下图总结了这个过程（我们想象 do_slabs_newslab(n) 被调用了两次）</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*7eiTeSuDXDUn1Sd_.png" /></figure><p>接下来我们来看在第6）步中一块 <strong>slab</strong> 是如何被初始化的。</p><h4>split_slab_page_into_freelist</h4><pre>static void split_slab_page_into_freelist(char *ptr, const unsigned int id) {<br>    slabclass_t *p = &amp;slabclass[id];<br>    int x;<br>    for (x = 0; x &lt; p-&gt;perslab; x++) {<br>        do_slabs_free(ptr, 0, id);<br>        ptr += p-&gt;size;<br>    }<br>}</pre><p>这个函数会遍历 <strong>slab</strong> 里的所有 <strong>item 块</strong>（slabclass_t.size），然后调用 do_slabs_free 来初始化每个 <strong>item 块</strong>的元数据。换一个说法，就是 “拆分 slab到待分配列表”-“split a slab into item free list”。你也许已经猜到了，这个 <em>待分配列表</em> 会被直接用于 <strong>对象</strong>分配，这个过程后面会详细讨论。</p><h4>do_slabs_free</h4><pre>static void do_slabs_free(void *ptr, const size_t size, unsigned int id) {<br>    slabclass_t *p;<br>    item *it;<br>...<br>    p = &amp;slabclass[id];<br><br>    it = (item *)ptr;<br>    it-&gt;it_flags = ITEM_SLABBED; // scr: ---------------&gt; 1)<br>    it-&gt;slabs_clsid = 0;<br>    it-&gt;prev = 0; // scr: ------------------------------&gt; 2)<br>    it-&gt;next = p-&gt;slots;<br>    if (it-&gt;next) it-&gt;next-&gt;prev = it;<br>    p-&gt;slots = it;<br><br>    p-&gt;sl_curr++; // scr: ------------------------------&gt; 3)<br>    p-&gt;requested -= size;<br>    return;<br>}</pre><p>技术上讲，这个函数处理的 <a href="https://holmeshe.me/cn/understanding-memcached-source-code-II/#">元数据</a> 元数据存在于每个 <strong>item 块</strong>的开始。</p><p>1）初始化一些域。这里 item 是另一个核心数据结构，后续会讨论。</p><p>2）将 <strong>item</strong> 加入到上述的 待分配列表 ，并且更新链表表头，slabclass_t.slots。</p><p>3）更新可分配项目数量，slabclass_t.sl_curr；并且更新 slabclass_t.requested 负责统计。注意这里并没有真正的释放对象，所以传入的 size 是0。</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*rLcps_-LGnMmrxIG.png" /></figure><h3>Slab preallocate</h3><p>下面我们来看 do_slabs_newslab 怎么使用。其中一个地方是之前看到过的 <a href="https://holmeshe.me/cn/understanding-memcached-source-code-II/#">slabs_init</a>（preallocate 设置为 true），</p><pre>static void slabs_preallocate (const unsigned int maxslabs) {<br>    int i;<br>    unsigned int prealloc = 0;<br><br>    /* pre-allocate a 1MB slab in every size class so people don&#39;t get<br>       confused by non-intuitive &quot;SERVER_ERROR out of memory&quot;<br>       messages.  this is the most common question on the mailing<br>       list.  if you really don&#39;t want this, you can rebuild without<br>       these three lines.  */<br><br>    for (i = POWER_SMALLEST /* scr: 1 */; i &lt; MAX_NUMBER_OF_SLAB_CLASSES; i++) {<br>        if (++prealloc &gt; maxslabs)<br>            return;<br>        if (do_slabs_newslab(i) == 0) {<br>            fprintf(stderr, &quot;Error while preallocating slab memory!\n&quot;<br>                &quot;If using -L or other prealloc options, max memory must be &quot;<br>                &quot;at least %d megabytes.\n&quot;, power_largest);<br>            exit(1);<br>        }<br>    }<br><br>}</pre><p>这个方法从POWER_SMALLEST（1）开始遍历所有的 <a href="https://holmeshe.me/cn/understanding-memcached-source-code-I/#core_ds">slabclass</a>，然后给每个 <strong>Slab组</strong> 预分配一个 <strong>slab</strong>。（下标为0th 的 <strong>Slab组</strong> 是一个特殊的组，存储空闲的 <strong>slab</strong> 用于上面提到的 <em>再平衡</em> 策略）。</p><h3>References</h3><p>和<a href="https://holmeshe.me/cn/understanding-memcached-source-code-I/#References">上文</a>一样。</p><p><em>Originally published at </em><a href="https://holmeshe.me/cn/understanding-memcached-source-code-II/"><em>holmeshe.me</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e24e4074ef89" width="1" height="1" alt=""><hr><p><a href="https://medium.com/source-code/%E7%90%86%E8%A7%A3-memcached-slab-ii-e24e4074ef89">理解 Memcached — Slab II</a> was originally published in <a href="https://medium.com/source-code">source code</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[理解 Memcached — Slab I]]></title>
            <link>https://medium.com/source-code/%E7%90%86%E8%A7%A3-memcached-slab-i-dca0f61d1226?source=rss-63f89bf0f9b4------2</link>
            <guid isPermaLink="false">https://medium.com/p/dca0f61d1226</guid>
            <category><![CDATA[中文]]></category>
            <category><![CDATA[cache]]></category>
            <category><![CDATA[open-source]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Holmes He]]></dc:creator>
            <pubDate>Sun, 24 Mar 2019 05:18:52 GMT</pubDate>
            <atom:updated>2019-03-24T05:39:11.539Z</atom:updated>
            <content:encoded><![CDATA[<h3>理解 Memcached源码 — Slab I</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/1*nHu8BDJxBLn0wzi5AXDgVQ.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/photos/pGM4sjt_BdQ?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Brooke Lark</a> on <a href="https://unsplash.com/search/photos/cake?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a></figcaption></figure><p>Slab分配器是这个缓存系统的核心，并在很大程度上决定了核心资源 — 内存 — 的利用效率。其它的三个部分，用来淘汰（超时）对象的LRU算法；和基于libevent的事件驱动；以及用于分布数据的一致性哈希，可以看作是围绕Slab来开发的。</p><p>在其他系统，比如内核，都能看到 Slab 分配器 的身影。无论它出现在哪里，都是为了对抗同一个性能问题，内存碎片。而本文就主要讨论 Slab 分配器 在memcached 中的实现（废话）。</p><p><strong>memcached version: 1.4.28</strong></p><p>首先我们来回答一些问题。</p><h3>前言</h3><p><strong>Slab</strong>翻译过来就是（一块）板子，具体来说，它是是被预先分配好的，大小为1M的内存块。这些板子可以被进一步分割成一些相同大小的小块，对象就存写在每一个小块上面。板子们会根据所存储对象的大小分成<strong>Slab组</strong>（<strong>slab class</strong>）。</p><h4>刚刚提到的内存碎片是啥</h4><p>具体来说，Slab 分配器 解决的其实是 内在碎片 （internal memory fragmentation）。这种碎片存在于分配的内存单元的内部。拿内核来说，内存的分配单元叫页（page），所有的内存分配的请求本质上都是在页里面拿走一块，同时产生的碎片也就自然产生于每页的内部了。</p><blockquote><em>和内在碎片不一样，外在碎片（external memory fragmentation）则存在于分配的内存单元之间。解决外在碎片的一般做法则是用buddy，就不在本文范围内了。</em></blockquote><p>我们再看下制造内存碎片过程，</p><p>1）malloc一堆小对象，</p><p>2）随机free一些上述小对象。</p><p>于是本来是整片的内存就会出现很多空洞，这些空洞，或者说碎片，因为太小而且分散，大概率永远无法被后续的malloc利用。</p><h4>内存碎片引起的问题</h4><p>继续往后说。这些碎片由于不能被 malloc 使用，基本也就和 内存泄漏 差不多了。引发的具体问题也差不多 — 定期重启。</p><h4>怎么办</h4><p><strong>Slab 分配器</strong> 并不消除内存碎片，而是将它们收敛起来，并锁定在某个固定的内存区域。具体来说，1）将大小相近的对象分<strong>组</strong>；2）同一<strong>组</strong>的的对象只会用该组的<strong>Slab</strong>（<strong>slab class</strong>）来分配内存。</p><p>接下来看代码。</p><p><strong>reminder: memcached version is 1.4.28</strong></p><p>核心数据结构：</p><pre>typedef struct {<br>    unsigned int size;      /* sizes of items */<br>    unsigned int perslab;   /* how many items per slab */<br><br>    void *slots;           /* list of item ptrs */<br>    unsigned int sl_curr;   /* total free items in list */<br><br>    unsigned int slabs;     /* how many slabs were allocated for this class */<br><br>    void **slab_list;       /* array of slab pointers */<br>    unsigned int list_size; /* size of prev array */<br><br>    size_t requested; /* The number of requested bytes */<br>} slabclass_t;<br><br>static slabclass_t slabclass[MAX_NUMBER_OF_SLAB_CLASSES];</pre><h3>模块初始化</h3><p>本节我们来看slabs_init，和 slabclass[MAX_NUMBER_OF_SLAB_CLASSES] 的初始化。 这个函数主要给 slabclass_t.size ，和 slabclass_t.perslab 赋值。第一个域表示 Slab 组 所对应的对象大小，第二个域则表示一个 Slab 上可以放多少个该类的对象。最后，slabs_init 是在系统初始化的过程被调用（如以下代码），</p><p>在这个阶段，slab_sizes 和 settings.factor 共同决定了后续逻辑的走向，并且确定各个 <strong>Slab组</strong> 所存储的对象大小，</p><p>如果 slab_sizes 不是 NULL, 用此数组的里面的值直接初始化各 Slab组 所对应的对象大小（支线a）；</p><p>反之，则用base size×n×settings.factor 来初始化上述的目标。这里 n 是 slabclass 的下标（支线b）。</p><p>除了写死的默认值，上述两个变量也能用 命令行参数赋值 。</p><p>本函数的另外两个参数 settings.maxbytes 和 preallocate ，会在 <a href="https://holmeshe.me/cn/understanding-memcached-source-code-II">后续</a> 讨论。这里我们假设 preallocate 为 false，并忽略其对应的逻辑。</p><p>下面我们来看 slabs_init 本身。</p><pre>void slabs_init(const size_t limit, const double factor, const bool prealloc, const uint32_t *slab_sizes) {<br>    int i = POWER_SMALLEST /* scr: 1 */ - 1;<br>    unsigned int size = sizeof(item) + settings.chunk_size; // b 1)<br>...<br>    memset(slabclass, 0, sizeof(slabclass));<br><br>    while (++i &lt; MAX_NUMBER_OF_SLAB_CLASSES-1) {<br>        if (slab_sizes != NULL) { // scr: -------------------&gt; a 1)<br>            if (slab_sizes[i-1] == 0)<br>                break;<br>            size = slab_sizes[i-1];<br>        } else if (size &gt;= settings.item_size_max / factor) {<br>            break;<br>        }<br>        /* Make sure items are always n-byte aligned */<br>        if (size % CHUNK_ALIGN_BYTES) // scr: -----------------&gt; 2)<br>            size += CHUNK_ALIGN_BYTES - (size % CHUNK_ALIGN_BYTES);<br><br>        slabclass[i].size = size;<br>        slabclass[i].perslab = settings.item_size_max / slabclass[i].size; // -----------------------------------------&gt; 3)<br>        if (slab_sizes == NULL)<br>            size *= factor; // scr: -------------------------&gt; b 4)<br>        if (settings.verbose &gt; 1) {<br>            fprintf(stderr, &quot;slab class %3d: chunk size %9u perslab %7u\n&quot;,<br>                    i, slabclass[i].size, slabclass[i].perslab);<br>        }<br>    }<br>    // scr: ---------------------------------------------------&gt; 5)<br>    power_largest = i;<br>    slabclass[power_largest].size = settings.item_size_max;<br>    slabclass[power_largest].perslab = 1;<br>...<br>}</pre><h4>支线 a</h4><p>1) 使用 slab_sizes 里面的值；</p><p>2) 将 size 用 CHUNK_ALIGN_BYTES 对其，并赋值给 slabclass[i].size；</p><p>3) 计算 slabclass[i].perslab;</p><p>5) 用 settings.item_size_max 初始化最后一个 <strong>Slab组</strong>。</p><p>这里要注意 settings.item_size_max 是 <strong>slab</strong> 本身的大小，也即是 <strong>memcached</strong> 能存的最大对象。类似的，settings.item_size_max 也可以在 运行时 确定</p><h4>Route b</h4><p>1) 用 settings.chunk_size 加上给每个对象附着的元数据（meta data）来计算基础大小（对象 item 会在后面讨论）；</p><p>2) 将 size 用 CHUNK_ALIGN_BYTES 对其，并赋值给 slabclass[i].size（同支线a）；</p><p>3) 计算 slabclass[i].perslab（同支线a）；</p><p>4) 用 factor(settings.factor) 计算下一个 <strong>Slab</strong> 组 的大小；</p><p>5) 用 settings.item_size_max 初始化最后一个 <strong>Slab组</strong>。</p><h3>References</h3><p><a href="https://github.com/memcached/memcached/wiki">memcached wiki</a></p><p><a href="http://gihyo.jp/dev/feature/01/memcached/0002">第2回 memcachedのメモリストレージを理解する</a></p><p><a href="https://blog.csdn.net/initphp/article/details/44888555">Memcached源码分析之存储机制Slabs（7）</a></p><p><a href="https://gokulvasanblog.wordpress.com/2016/07/11/understanding-malloc-part1/">Understanding Malloc</a></p><p><a href="https://www.kernel.org/doc/gorman/html/understand/understand011.html">Ch8 — Slab Allocator</a></p><p><a href="https://www.usenix.org/legacy/publications/library/proceedings/bos94/full_papers/bonwick.a">The Slab Allocator:An Object-Caching Kernel Memory Allocator</a></p><p><em>Originally published at </em><a href="https://holmeshe.me/cn/understanding-memcached-source-code-I/"><em>holmeshe.me</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=dca0f61d1226" width="1" height="1" alt=""><hr><p><a href="https://medium.com/source-code/%E7%90%86%E8%A7%A3-memcached-slab-i-dca0f61d1226">理解 Memcached — Slab I</a> was originally published in <a href="https://medium.com/source-code">source code</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Understanding The Memcached Source Code-Event Driven II]]></title>
            <link>https://medium.com/source-code/understanding-the-memcached-source-code-event-driven-ii-8d6249d62943?source=rss-63f89bf0f9b4------2</link>
            <guid isPermaLink="false">https://medium.com/p/8d6249d62943</guid>
            <category><![CDATA[english-posts]]></category>
            <category><![CDATA[cache]]></category>
            <category><![CDATA[memcached]]></category>
            <category><![CDATA[open-source]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Holmes He]]></dc:creator>
            <pubDate>Sat, 16 Mar 2019 23:15:16 GMT</pubDate>
            <atom:updated>2019-03-17T01:21:59.563Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*VsFAiXHsRdwUM9jjhk85eg.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/photos/1Hh57OhkdCc?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Toa Heftiba</a> on <a href="https://unsplash.com/search/photos/cake?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a></figcaption></figure><blockquote>Slab allocator is the core module of the cache system, which largely determines how efficient the bottleneck resource, memory, can be utilised. The other 3 parts, namely, LRU algorithm for entry expiration; and an event driven model based on libevent; and the consistent harsh for data distribution, are built around it.</blockquote><p><a href="https://medium.com/source-code/understanding-the-memcached-source-code-slab-i-9199de613762">Slab I</a><br><a href="https://medium.com/source-code/understanding-the-memcached-source-code-slab-ii-6477c0482548">Slab II</a><br><a href="https://medium.com/source-code/https-medium-com-source-code-understanding-the-memcached-source-code-slab-iii-cb06e577d73e">Slab III</a><br><a href="https://medium.com/source-code/understanding-the-memcached-source-code-lru-i-8b383c561638">LRU I</a><br><a href="https://medium.com/source-code/understanding-the-memcached-source-code-lru-ii-ea4067863652">LRU II</a><br><a href="https://medium.com/source-code/understanding-the-memcached-source-code-lru-iii-87d1c7497cb9">LRU III</a><br><a href="https://medium.com/source-code/understanding-the-memcached-source-code-event-driven-i-cd6c947c4092">Event driven I</a><br>Event driven II (this article)</p><p>In classic <em>multithreading</em>, blocking I/O operations constrain the maximum number of requests a server can handle. Hence asynchronous <strong>event driven</strong> model is used to eliminate the throughput bottleneck. As such, the synchronous and potentially slow process is divided into logic segments that are free of I/O, and are executed asynchronously.</p><p>When it comes to asynchronisation, extra space is required to store <em>context</em>s. This is because the logic segments, that could be associated with different <em>session</em>s, are executed in an interleaved way. For instance, in the case when asynchronisation is implemented (emulated) using synchronous <em>multithreading</em>, the “extra space” is in the form of thread stack. Whilst <em>context</em>s are maintained in user land in <strong>event driven</strong>.</p><p>conn is the representative of those <em>context</em>s in <strong>Memcached</strong>.</p><h3>Core data structure — conn</h3><pre>typedef struct conn conn;<br>struct conn {<br>    int    sfd;<br><br>...// scr: not applicable<br><br>    enum conn_states  state;<br><br>...// scr: not applicable<br><br>    struct event event;<br>    short  ev_flags;<br>    short  which;   /** which events were just triggered */<br><br>    char   *rbuf;   /** buffer to read commands into */<br>    char   *rcurr;  /** but if we parsed some already, this is where we stopped */<br>    int    rsize;   /** total allocated size of rbuf */<br>    int    rbytes;  /** how much data, starting from rcur, do we have unparsed */<br><br>    char   *wbuf;<br>    char   *wcurr;<br>    int    wsize;<br>    int    wbytes;<br>    /** which state to go into after finishing current write */<br>    enum conn_states  write_and_go;<br>    void   *write_and_free; /** free this memory after finishing writing */<br><br>    char   *ritem;  /** when we read in an item&#39;s value, it goes here */<br>    int    rlbytes;<br><br>    /* data for the nread state */<br><br>    /**<br>     * item is used to hold an item structure created after reading the command<br>     * line of set/add/replace commands, but before we finished reading the actual<br>     * data. The data is read into ITEM_data(item) to avoid extra copying.<br>     */<br><br>    void   *item;     /* for commands set/add/replace  */<br><br>    /* data for the swallow state */<br>    int    sbytes;    /* how many bytes to swallow */<br><br>    /* data for the mwrite state */<br>    struct iovec *iov;<br>    int    iovsize;   /* number of elements allocated in iov[] */<br>    int    iovused;   /* number of elements used in iov[] */<br><br>    struct msghdr *msglist;<br>    int    msgsize;   /* number of elements allocated in msglist[] */<br>    int    msgused;   /* number of elements used in msglist[] */<br>    int    msgcurr;   /* element in msglist[] being transmitted now */<br>    int    msgbytes;  /* number of bytes in current msg */<br><br>    item   **ilist;   /* list of items to write out */<br>    int    isize;<br>    item   **icurr;<br>    int    ileft;<br><br>...// scr: not applicable<br><br>    enum protocol protocol;   /* which protocol this connection speaks */<br><br>...// scr: not applicable<br><br>    socklen_t request_addr_size;<br>    unsigned char *hdrbuf; /* udp packet headers */<br>    int    hdrsize;   /* number of headers&#39; worth of space is allocated */<br><br>    bool   noreply;   /* True if the reply should not be sent. */<br><br>...// scr: not applicable<br><br>    short cmd; /* current command being processed */<br><br>...// scr: not applicable<br><br>    int keylen;<br>    conn   *next;     /* Used for generating a list of conn structures */<br>    LIBEVENT_THREAD *thread; /* Pointer to the thread object serving this connection */<br>};</pre><h4>Properties in use</h4><p>fd - the file descriptor a <strong>event</strong> is rooted. used by <a href="https://holmeshe.me/understanding-memcached-source-code-VII/">last post</a></p><p>state - the main focus of this post</p><p>rbytes - size of data to be processed. initialised by <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#try-read-network">try_read_network</a>, updated by <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#process-get-command">process_get_command</a>, used by <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#try-read-command">try_read_command</a></p><p>rsize - current size of the <em>read buffer</em>. used by <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#try-read-network">try_read_network</a></p><p>rbuf - <em>read buffer</em> address. used by <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#try-read-network">try_read_network</a></p><p>rcurr - address of unprocessed data. used by <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#try-read-network">try_read_network</a></p><p>last_cmd_time - updated when start processing a command. used by <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#try-read-network">try_read_network</a></p><p>ilist - the <strong>item</strong> list that is associated with the context; icurr and ileft indicate the current entry and number of entries left. used by <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#process-get-command">process_get_command</a>, <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#Finish-read">conn_release_items</a></p><p>iov - the actual storage for pointers of output data, which is used by msglist; iovsize, and iovused are its allocated size and used size respectively. initialised by <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#try-read-command">process_command</a>, used by <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#add-iov">add_iov</a>, <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#add-iov">ensure_iov_space</a></p><blockquote>Here the data structures (struct msghdr and struct iovec) is required by <a href="http://man7.org/linux/man-pages/man3/sendmsg.3p.html">sendmsg</a>. The relevant text about the API is pasted bellow.</blockquote><blockquote><em>The msg_iov and msg_iovlen fields of message specify zero or more buffers containing the data to be sent. msg_iov points to an array of iovec structures; msg_iovlen shall be set to the dimension of this array. In each iovec structure, the iov_base field specifies a storage area and the iov_len field gives its size in bytes. Some of these sizes can be zero. The data from each storage area indicated by msg_iov is sent in turn…</em></blockquote><p>msglist - the list that stores the struct msghdr themselves; msgsize and msgused are its allocated size and used size respectively; msgbytes indicates totall size of the output data size; msgcurr points to the index that has been processed (written).</p><blockquote><em>Yet nothing is bette than a chart to demonstrate the data structures and the layout in memory.</em></blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*1beFby05ZpaDPy9U.png" /><figcaption>msglist &amp; iov</figcaption></figure><h4>State switch</h4><p>An <strong>event</strong> triggers cascading changes of states which in turn invokes various procedures, before <strong>drive machine</strong> relinquishes control and waits for a new <strong>event</strong> arrival. In <a href="https://holmeshe.me/understanding-memcached-source-code-VII/">last post</a>, we have seen this process on <em>dispatch thread</em>, in which</p><p>1) conn_listening is triggered by a new connection;</p><p>2) <a href="https://holmeshe.me/understanding-memcached-source-code-VII/#dispatch-conn-new">dispatch_conn_new</a> is invoked, which transfer the new accepted fd, as well as succeeding <strong>event</strong>s to one of the <em>worker thread</em>s;</p><p>3) <em>dispatch thread</em> gives up CPU and waits for new “new connection” <strong>event</strong>s.</p><p>In this post, we are going to see more complex <em>state switch</em>es that effectively link together the procedures we discussed in <a href="https://holmeshe.me/understanding-memcached-source-code-VI/">LRU III</a>,</p><blockquote>The <strong>state</strong> of a given session is represented by conn.state of its associated <em>context</em>.</blockquote><p>and this time we are going to adopt a similar approach as <a href="https://holmeshe.me/understanding-memcached-source-code-VI/">LRU III</a>, i.e., sending <em>telnet commands</em> to a <strong>Memcached</strong> instance, to navigate the outermost layer of the <strong>Memcached</strong> application.</p><blockquote>We will also switch ON the convenient <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#">verbose</a> with -vvv to better observe the internal state transitions.</blockquote><h3>Read</h3><p>Firstly (as usual) we <em>telnet</em> to the <strong>Memcached</strong> instance, and add some <strong>item</strong>s</p><pre>…<br>~telnet localhost 11211<br>Trying 127.0.0.1…<br>Connected to localhost.<br>Escape character is ‘^]’.<br>…</pre><p><strong>Memcached </strong>output</p><pre>…<br>&lt; 36 new auto-negotiating client connection<br>…</pre><blockquote>Here 36 is the accepted fd. As mentioned, the following operations will be on this fd.</blockquote><p>Next we send the exact same read command to the <strong>Memcached</strong> instance as in <a href="https://holmeshe.me/understanding-memcached-source-code-VI/#Read">LRU III</a></p><pre>&gt; get test</pre><p><strong>Memcached </strong>output</p><pre>…<br>36: going from conn_new_cmd to conn_waiting<br>36: going from conn_waiting to conn_read<br>36: going from conn_read to conn_parse_cmd<br>36: Client using the ascii protocol<br>&lt; 36 get test<br>&gt; FOUND KEY test<br>&gt; 36 sending key test<br>&gt; 36 END<br>36: going from conn_parse_cmd to conn_mwrite<br>36: going from conn_mwrite to conn_new_cmd<br>36: going from conn_new_cmd to conn_waiting<br>36: going from conn_waiting to conn_read<br>…</pre><p>As mentioned in <a href="https://holmeshe.me/understanding-memcached-source-code-VII/#event-handler">last post</a>, the initial state of <em>worker thread</em>s is</p><h4>conn_new_cmd</h4><p>so we get started from here.</p><pre>...<br>static void drive_machine(conn *c) {<br>    int nreqs = settings.reqs_per_event; // scr: --------&gt; 1)<br>...<br>        case conn_new_cmd:<br>            /* Only process nreqs at a time to avoid starving other<br>               connections */<br>            --nreqs; // scr: ----------------------------&gt; 1)<br>            if (nreqs &gt;= 0) {<br>                reset_cmd_handler(c); // scr: -----------&gt; 2)<br>            } else {<br>                pthread_mutex_lock(&amp;c-&gt;thread-&gt;stats.mutex);<br>                c-&gt;thread-&gt;stats.conn_yields++;<br>                pthread_mutex_unlock(&amp;c-&gt;thread-&gt;stats.mutex);<br>                if (c-&gt;rbytes &gt; 0) {<br>...// scr: error handling<br>                }<br>                stop = true; // scr: --------------------&gt; 3)<br>            }<br>            break;<br>...<br><br>static void reset_cmd_handler(conn *c) {<br>    c-&gt;cmd = -1;<br>    c-&gt;substate = bin_no_state;<br>    if(c-&gt;item != NULL) {<br>        item_remove(c-&gt;item);<br>        c-&gt;item = NULL;<br>    }<br>    conn_shrink(c);<br>    if (c-&gt;rbytes &gt; 0) {<br>        conn_set_state(c, conn_parse_cmd); // scr: -----&gt; 2a)<br>    } else {<br>        conn_set_state(c, conn_waiting); // scr: -------&gt; 2b)<br>    }<br>}</pre><p>1) nreqs (settings.reqs_per_event) is the maximum requests one <em>event loop</em> iteration should handle. Note that the threshold is needed because new connections will not be handled if one <em>event loop</em> iteration takes too long to complete. Note also that the connection being interrupted will be fired again and get the chance to enter the <strong>drive machine</strong> with a “read” event since the descriptor is set with EV_PERSIST in the <a href="https://holmeshe.me/understanding-memcached-source-code-VII/#event-handler">last post</a>.</p><p>2) Reset the relevant properties in the <em>context</em> for a new command.</p><p>2a) Handles the case when the event driven is entered with a “read” event.</p><p>2b) Handles the case when the event driven is entered with a “new connection” event.</p><p>3) Yield the current iteration when the threshold is reached.</p><h4>conn_waiting</h4><pre>...<br>        case conn_waiting:<br>            if (!update_event(c, EV_READ | EV_PERSIST)) {<br>                if (settings.verbose &gt; 0)<br>                    fprintf(stderr, &quot;Couldn&#39;t update event\n&quot;);<br>                conn_set_state(c, conn_closing);<br>                break;<br>            }<br><br>            conn_set_state(c, conn_read);<br>            stop = true;<br>            break;<br>...</pre><p>Simply reset the descriptor with the original flags (i.e., EV_READ, EV_PERSIST), update the state of the <em>context</em> to the next hop (conn_read), and relinquish the CPU.</p><h4>conn_read</h4><pre>...<br>case conn_read:<br>    res = IS_UDP(c-&gt;transport) ? try_read_udp(c) : try_read_network(c); //1)<br><br>    switch (res) {<br>    case READ_NO_DATA_RECEIVED:<br>        conn_set_state(c, conn_waiting);<br>        break;<br>    case READ_DATA_RECEIVED:<br>        conn_set_state(c, conn_parse_cmd); // scr: -------------&gt; 2)<br>        break;<br>    case READ_ERROR:<br>        conn_set_state(c, conn_closing);<br>        break;<br>    case READ_MEMORY_ERROR: /* Failed to allocate more memory */<br>        /* State already set by try_read_network */<br>        break;<br>    }<br>    break;<br>...</pre><p>1) Read from the file descriptor and save the data to the <em>context</em>.</p><p>2) Switch to the next state, conn_parse_cmd.</p><h4>try_read_network</h4><pre>static enum try_read_result try_read_network(conn *c) {<br>    enum try_read_result gotdata = READ_NO_DATA_RECEIVED;<br>    int res;<br>    int num_allocs = 0;<br>    assert(c != NULL);<br><br>    if (c-&gt;rcurr != c-&gt;rbuf) { // scr: -------------------------&gt; 1)<br>        if (c-&gt;rbytes != 0) /* otherwise there&#39;s nothing to copy */<br>            memmove(c-&gt;rbuf, c-&gt;rcurr, c-&gt;rbytes);<br>        c-&gt;rcurr = c-&gt;rbuf;<br>    }<br><br>    while (1) {<br>        if (c-&gt;rbytes &gt;= c-&gt;rsize) { // scr: -------------------&gt; 2)<br>            if (num_allocs == 4) {<br>                return gotdata;<br>            }<br>            ++num_allocs;<br>            char *new_rbuf = realloc(c-&gt;rbuf, c-&gt;rsize * 2);<br>            if (!new_rbuf) {<br>...// scr: error handling<br>            }<br>            c-&gt;rcurr = c-&gt;rbuf = new_rbuf;<br>            c-&gt;rsize *= 2;<br>        }<br><br>        int avail = c-&gt;rsize - c-&gt;rbytes; // scr: --------------&gt; 3)<br>        res = read(c-&gt;sfd, c-&gt;rbuf + c-&gt;rbytes, avail);<br>        if (res &gt; 0) {<br>...// scr: stat<br>            gotdata = READ_DATA_RECEIVED;<br>            c-&gt;rbytes += res;<br>            if (res == avail) { // scr: -----------------------&gt; 3a)<br>                continue;<br>            } else {<br>                break; // scr: --------------------------------&gt; 3b)<br>            }<br>        }<br>        if (res == 0) {<br>            return READ_ERROR;<br>        }<br>        if (res == -1) {<br>            if (errno == EAGAIN || errno == EWOULDBLOCK) { //src:3b)<br>                break;<br>            }<br>            return READ_ERROR;<br>        }<br>    }<br>    return gotdata;<br>}</pre><p>Here the while (1) is used to handle logic flow for buffer expanding instead of loop.</p><p>1) Move rcurr to the beginning of the <em>read buffer</em>.</p><p>2) If the data size exceeds the <em>read buffer</em> size, try expanding the buffer (for at most 4 times).</p><p>3) Calculate the available buffer space for <a href="http://man7.org/linux/man-pages/man2/read.2.html">read</a>ing from the socket, and update rbytes accordingly.</p><p>3a) Goto 2) if the buffer is full.</p><p>3b) Return READ_DATA_RECEIVED, which switches the state to conn_parse_cmd in the <strong>state machine</strong> pass through.</p><h4>conn_parse_cmd</h4><pre>...<br>case conn_parse_cmd :<br>    if (try_read_command(c) == 0) {<br>        /* wee need more data! */<br>        conn_set_state(c, conn_waiting);<br>    }<br><br>    break;<br>...</pre><h4>try_read_command</h4><pre>static int try_read_command(conn *c) {<br>    assert(c != NULL);<br>    assert(c-&gt;rcurr &lt;= (c-&gt;rbuf + c-&gt;rsize));<br>    assert(c-&gt;rbytes &gt; 0);<br><br>    if (c-&gt;protocol == negotiating_prot || c-&gt;transport == udp_transport)  {<br>        if ((unsigned char)c-&gt;rbuf[0] == (unsigned char)PROTOCOL_BINARY_REQ) {<br>            c-&gt;protocol = binary_prot;<br>        } else {<br>            c-&gt;protocol = ascii_prot; // scr: ------------------&gt; 1)<br>        }<br><br>        if (settings.verbose &gt; 1) { // scr: --------------------&gt; ~)<br>            fprintf(stderr, &quot;%d: Client using the %s protocol\n&quot;, c-&gt;sfd,<br>                    prot_text(c-&gt;protocol));<br>        }<br>    }<br><br>    if (c-&gt;protocol == binary_prot) {<br>...// scr: not applicable<br>    } else {<br>        char *el, *cont;<br><br>        if (c-&gt;rbytes == 0)<br>            return 0;<br><br>        el = memchr(c-&gt;rcurr, &#39;\n&#39;, c-&gt;rbytes); // scr: --------&gt; 2)<br>        if (!el) {<br>...// scr: not applicable<br>        }<br>        cont = el + 1;<br>        if ((el - c-&gt;rcurr) &gt; 1 &amp;&amp; *(el - 1) == &#39;\r&#39;) {<br>            el--;<br>        }<br>        *el = &#39;\0&#39;; // scr: ------------------------------------&gt; 2)<br><br>        assert(cont &lt;= (c-&gt;rcurr + c-&gt;rbytes));<br><br>        c-&gt;last_cmd_time = current_time; // scr: ---------------&gt; 3)<br>        process_command(c, c-&gt;rcurr); // scr: ------------------&gt; 4)<br><br>        c-&gt;rbytes -= (cont - c-&gt;rcurr); // scr: ----------------&gt; 5)<br>        c-&gt;rcurr = cont; // scr: -------------------------------&gt; 6)<br><br>        assert(c-&gt;rcurr &lt;= (c-&gt;rbuf + c-&gt;rsize));<br>    }<br><br>    return 1;<br>}</pre><p>1) Determine the protocol type, in this case is ascii_prot.</p><p>~) Verbose message we saw in the beginning.</p><p>2) Trim all the &#39;\n&#39; and &#39;\r&#39; in the end, store the position of the command last character to el, and store the command end to cont.</p><p>3) Update last_cmd_time.</p><p>4) Call process_command which locates the “get” command and call process_get_command. In process_command, a) tokenize_command is a string parsing method that stores command (i.e., “get”) in tokens[COMMAND_TOKEN] and key (i.e., test) in tokens[KEY_TOKEN]; b) initialisation of msgcurr, msgused, iovused; c) initialisation other fields in <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#add-msghdr">add_msghdr</a>; and d) <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#process-get-command">process_get_command</a> is the next step.</p><p>5) Update rbytes with the length of the command that has been processed (cont - c-&gt;rcurr).</p><p>6) Move the rcurr to the unprocessed data located at end of the command portion.</p><h4>add_msghdr</h4><p>Before the logic reaches <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#process-get-command">process_get_command</a>, an entry should be initialised in msglist for the current command.</p><pre>static int add_msghdr(conn *c)<br>{<br>    struct msghdr *msg;<br><br>    assert(c != NULL);<br><br>    if (c-&gt;msgsize == c-&gt;msgused) { // scr: --------------------&gt; 1)<br>        msg = realloc(c-&gt;msglist, c-&gt;msgsize * 2 * sizeof(struct msghdr));<br>        if (! msg) {<br>            STATS_LOCK();<br>            stats.malloc_fails++;<br>            STATS_UNLOCK();<br>            return -1;<br>        }<br>        c-&gt;msglist = msg;<br>        c-&gt;msgsize *= 2;<br>    }<br><br>    msg = c-&gt;msglist + c-&gt;msgused; // scr: ---------------------&gt; 2)<br><br>    /* this wipes msg_iovlen, msg_control, msg_controllen, and<br>       msg_flags, the last 3 of which aren&#39;t defined on solaris: */<br>    memset(msg, 0, sizeof(struct msghdr)); // scr: -------------&gt; 3)<br><br>    msg-&gt;msg_iov = &amp;c-&gt;iov[c-&gt;iovused]; // scr: ----------------&gt; 3)<br><br>    if (IS_UDP(c-&gt;transport) &amp;&amp; c-&gt;request_addr_size &gt; 0) {<br>...// scr: UDP related<br>    }<br><br>    c-&gt;msgbytes = 0; // scr: -----------------------------------&gt; 4)<br>    c-&gt;msgused++; // scr: --------------------------------------&gt; 5)<br><br>    if (IS_UDP(c-&gt;transport)) {<br>...// scr: UDP related<br>    }<br><br>    return 0;<br>}</pre><p>1) Expand the msglist when required.</p><p>2) Point to the next empty entry in msglist with msg.</p><p>3) Initialise the entry pointed by msg. Here the critical operation is msg-&gt;msg_iov = &amp;c-&gt;iov[c-&gt;iovused]; which links the msglist to the specific entry in iov. (<a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#fig_core_ds">Figure - msglist &amp; iov</a>)</p><p>4) Initialise msgbytes to 0.</p><p>5) Update msgused accordingly.</p><h4>process_get_command</h4><p>We have seen this method in beginning of <a href="https://holmeshe.me/understanding-memcached-source-code-VI/#process-get-command">LRU III</a>. This time, we will complete its pass through with the context of <strong>event driven</strong>.</p><pre>static inline void process_get_command(conn *c, token_t *tokens, size_t ntokens, bool return_cas) {<br>    char *key;<br>    size_t nkey;<br>    int i = 0;<br>    item *it;<br>    token_t *key_token = &amp;tokens[KEY_TOKEN];<br>    char *suffix;<br>    assert(c != NULL);<br><br>    do {<br>        while(key_token-&gt;length != 0) { // scr: ----------------&gt; 1)<br><br>            key = key_token-&gt;value;<br>            nkey = key_token-&gt;length;<br><br>            if(nkey &gt; KEY_MAX_LENGTH) {<br>                out_string(c, &quot;CLIENT_ERROR bad command line format&quot;);<br>                while (i-- &gt; 0) {<br>                    item_remove(*(c-&gt;ilist + i));<br>                }<br>                return;<br>            }<br><br>            it = item_get(key, nkey, c); // scr: ---------------&gt; 2)<br>            if (settings.detail_enabled) {<br>                stats_prefix_record_get(key, nkey, NULL != it);<br>            }<br>            if (it) {<br>                if (i &gt;= c-&gt;isize) { // scr: -------------------&gt; 3)<br>                    item **new_list = realloc(c-&gt;ilist, sizeof(item *) * c-&gt;isize * 2);<br>                    if (new_list) {<br>                        c-&gt;isize *= 2;<br>                        c-&gt;ilist = new_list;<br>                    } else {<br>...// scr: stat<br>                        item_remove(it);<br>                        break;<br>                    }<br>                }<br><br>                if (return_cas)<br>                {<br>...// scr: cas<br>                }<br>                else<br>                {<br>                  MEMCACHED_COMMAND_GET(c-&gt;sfd, ITEM_key(it), it-&gt;nkey,<br>                                        it-&gt;nbytes, ITEM_get_cas(it));<br>                  if (add_iov(c, &quot;VALUE &quot;, 6) != 0 || // scr: --&gt; 4)<br>                      add_iov(c, ITEM_key(it), it-&gt;nkey) != 0 ||<br>                      add_iov(c, ITEM_suffix(it), it-&gt;nsuffix + it-&gt;nbytes) != 0)<br>                      {<br>                          item_remove(it);<br>                          break;<br>                      }<br>                }<br><br>...// scr: verbose &amp; stat<br><br>                item_update(it); // scr: -----------------------&gt; 5)<br>                *(c-&gt;ilist + i) = it; // scr: ------------------&gt; 6)<br>                i++;<br><br>            } else {<br>...// scr: stat<br>            }<br><br>            key_token++; // scr: -------------------------------&gt; 1)<br>        }<br><br>        /*<br>         * If the command string hasn&#39;t been fully processed, get the next set<br>         * of tokens.<br>         */<br>        if(key_token-&gt;value != NULL) { // scr: -----------------&gt; 1)<br>            ntokens = tokenize_command(key_token-&gt;value, tokens, MAX_TOKENS);<br>            key_token = tokens;<br>        }<br><br>    } while(key_token-&gt;value != NULL);<br><br>    c-&gt;icurr = c-&gt;ilist; // scr: -------------------------------&gt; 6)<br>    c-&gt;ileft = i; scr: -----------------------------------------&gt; 6)<br>...// scr: cas &amp; verbose<br><br>    if (key_token-&gt;value != NULL || add_iov(c, &quot;END\r\n&quot;, 5) != 0<br>        || (IS_UDP(c-&gt;transport) &amp;&amp; build_udp_headers(c) != 0)) {<br>        out_of_memory(c, &quot;SERVER_ERROR out of memory writing get response&quot;);<br>    }<br>    else { // scr: ---------------------------------------------&gt; 7)<br>        conn_set_state(c, conn_mwrite);<br>        c-&gt;msgcurr = 0;<br>    }<br>}</pre><p>1) Iterate through key token array. Here we got one key token ‘test’.</p><p>2) Call <a href="https://holmeshe.me/understanding-memcached-source-code-VI/#do-item-get">item_get</a> for the <strong>item</strong> pointer.</p><p>3) Increase the ilist size if it is full, and . Here ilist stores the <strong>item</strong> being processed. In the <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#Finish-read">end of the current command processing</a>, this list is used to batch release the <strong>item</strong>s reference counts.</p><p>4) add_iov prepares the output of this session.</p><p>5) Call <a href="https://holmeshe.me/understanding-memcached-source-code-VI/#do-item-update">item_update</a> to manipulate the <em>LRU</em> lists.</p><p>6) Link the <strong>item</strong> currently being processed to ilist, and update the associated fields.</p><p>7) Move on to the next state <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#conn-mwrite">conn_mwrite</a>.</p><h4>add_iov</h4><pre>static int add_iov(conn *c, const void *buf, int len) {<br>    struct msghdr *m;<br>    int leftover;<br>    bool limit_to_mtu;<br><br>    assert(c != NULL);<br><br>    do {<br>        m = &amp;c-&gt;msglist[c-&gt;msgused - 1]; // scr: ---------------&gt; 1)<br><br>        /*<br>         * Limit UDP packets, and the first payloads of TCP replies, to<br>         * UDP_MAX_PAYLOAD_SIZE bytes.<br>         */<br>        limit_to_mtu = IS_UDP(c-&gt;transport) || (1 == c-&gt;msgused);<br><br>        /* We may need to start a new msghdr if this one is full. */<br>        if (m-&gt;msg_iovlen == IOV_MAX ||<br>            (limit_to_mtu &amp;&amp; c-&gt;msgbytes &gt;= UDP_MAX_PAYLOAD_SIZE)) {<br>            add_msghdr(c);<br>            m = &amp;c-&gt;msglist[c-&gt;msgused - 1]; // scr: -----------&gt; 7)<br>        }<br><br>        if (ensure_iov_space(c) != 0) // scr: ------------------&gt; 2)<br>            return -1;<br><br>        /* If the fragment is too big to fit in the datagram, split it up */<br>        if (limit_to_mtu &amp;&amp; len + c-&gt;msgbytes &gt; UDP_MAX_PAYLOAD_SIZE) {<br>            leftover = len + c-&gt;msgbytes - UDP_MAX_PAYLOAD_SIZE; //scr*)<br>            len -= leftover;<br>        } else {<br>            leftover = 0;<br>        }<br><br>        m = &amp;c-&gt;msglist[c-&gt;msgused - 1]; // scr: ---------------&gt; 1)<br>        m-&gt;msg_iov[m-&gt;msg_iovlen].iov_base = (void *)buf; // scr: -&gt; 3)<br>        m-&gt;msg_iov[m-&gt;msg_iovlen].iov_len = len;<br><br>        c-&gt;msgbytes += len; // scr: ----------------------------&gt; 4)<br>        c-&gt;iovused++; // scr: ----------------------------------&gt; 5)<br>        m-&gt;msg_iovlen++; // scr: -------------------------------&gt; 6)<br><br>        buf = ((char *)buf) + len;<br>        len = leftover;<br>    } while (leftover &gt; 0);<br><br>    return 0;<br>}</pre><p>This method initialised an entry on iov list and add it to the last in-use item in msglist (<a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#fig_core_ds">Figure - msglist &amp; iov</a>).</p><p>1) Get the tail of the in use portion of msglist.</p><p>2) Expend iov if necessary.</p><p>3) Initialize the iov_base and iov_len fields within the iov entry. Note that the msg_iov has been linked to the position of specific entry in iov, hence operations on msg_iov change the content of iov as well.</p><p>4) Update msgbytes with the total <strong>item</strong> size.</p><p>5, 6) Update iovused and msg_iovlen accordingly.</p><p>7) Handle <strong>MTU</strong> with the assistance of do while loop.</p><h4>conn_mwrite</h4><pre>...<br>        case conn_mwrite:<br>          if (IS_UDP(c-&gt;transport) &amp;&amp; c-&gt;msgcurr == 0 &amp;&amp; build_udp_headers(c) != 0) {<br>...// scr: UDP related<br>          }<br>            switch (transmit(c)) {<br>...// scr: state processing<br>            }<br>            break;<br>...</pre><p>Before explaining the logic <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#Back-to-state-processing">process of conn_mwrite state</a>, we look at the essential within first, which is</p><h4>transmit</h4><pre>static enum transmit_result transmit(conn *c) {<br>    assert(c != NULL);<br><br>    if (c-&gt;msgcurr &lt; c-&gt;msgused &amp;&amp;<br>            c-&gt;msglist[c-&gt;msgcurr].msg_iovlen == 0) { // scr: --&gt; 1)<br>        /* Finished writing the current msg; advance to the next. */<br>        c-&gt;msgcurr++;<br>    }<br>    if (c-&gt;msgcurr &lt; c-&gt;msgused) { // scr: ---------------------&gt; 2)<br>        ssize_t res;<br>        struct msghdr *m = &amp;c-&gt;msglist[c-&gt;msgcurr];<br>            <br>        res = sendmsg(c-&gt;sfd, m, 0); <br>        if (res &gt; 0) {<br>...// scr: state<br>            /* We&#39;ve written some of the data. Remove the completed<br>               iovec entries from the list of pending writes. */<br>            while (m-&gt;msg_iovlen &gt; 0 &amp;&amp; res &gt;= m-&gt;msg_iov-&gt;iov_len) {<br>                res -= m-&gt;msg_iov-&gt;iov_len;<br>                m-&gt;msg_iovlen--;<br>                m-&gt;msg_iov++;<br>            }   <br><br>            /* Might have written just part of the last iovec entry;<br>               adjust it so the next write will do the rest. */<br>            if (res &gt; 0) {<br>                m-&gt;msg_iov-&gt;iov_base = (caddr_t)m-&gt;msg_iov-&gt;iov_base + res;<br>                m-&gt;msg_iov-&gt;iov_len -= res;<br>            }<br>            return TRANSMIT_INCOMPLETE;<br>        }<br>        if (res == -1 &amp;&amp; (errno == EAGAIN || errno == EWOULDBLOCK)) { // scr: ------------------------------------------------------&gt; 3)<br>            if (!update_event(c, EV_WRITE | EV_PERSIST)) {<br>                if (settings.verbose &gt; 0)<br>                    fprintf(stderr, &quot;Couldn&#39;t update event\n&quot;);<br>                conn_set_state(c, conn_closing);<br>                return TRANSMIT_HARD_ERROR;<br>            }<br>            return TRANSMIT_SOFT_ERROR;<br>        }<br>        /* if res == 0 or res == -1 and error is not EAGAIN or EWOULDBLOCK,<br>           we have a real error, on which we close the connection */<br>        if (settings.verbose &gt; 0)<br>            perror(&quot;Failed to write, and not due to blocking&quot;);<br><br>        if (IS_UDP(c-&gt;transport))<br>...// scr: UDP related<br>        else<br>            conn_set_state(c, conn_closing);<br>        return TRANSMIT_HARD_ERROR; // scr: --------------------&gt; 4)<br>    } else {<br>        return TRANSMIT_COMPLETE; // scr: ----------------------&gt; 5)<br>    }<br>}</pre><p>As the essential method of state conn_mwrite processing, transmit goes through the msglist (starting from 0, the initial value) and tries its best to send out all the pending data accumulated in the current session. This is done within itself or in subsequent passes through the <em>event loop</em>. Only when blocking operation is indicated by EAGAIN or EWOULDBLOCK, the <strong>state machine</strong> stops the current <em>event loop</em> iteration, and the same session will be resumed when the buffer space becomes available again.</p><p>1) If the msg_iovlen is 0, the writing of msgcurr slot has finished, hence move to the next slot.</p><p>2) Call <a href="http://man7.org/linux/man-pages/man3/sendmsg.3p.html">sendmsg</a> and moves msg_iov, iov_base and iov_len according to the data length (res) that has been written successfully. This leads to case b) of the <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#Back-to-state-processing">state processing</a>.</p><p>3) As mentioned, EAGAIN or EWOULDBLOCK returned by <a href="http://man7.org/linux/man-pages/man3/sendmsg.3p.html">sendmsg</a> leads to case c) of <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#Back-to-state-processing">state processing</a>.</p><p>4) Errors other than the above two lead to case c) of <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#Back-to-state-processing">state processing</a>.</p><p>5) c-&gt;msgcurr &gt;= c-&gt;msgused means that write all data of the session finished, which leads to b) of the <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#Back-to-state-processing">state processing</a>.</p><h4>Back to state processing</h4><pre>...<br>        case conn_mwrite:<br>          if (IS_UDP(c-&gt;transport) &amp;&amp; c-&gt;msgcurr == 0 &amp;&amp; build_udp_headers(c) != 0) {<br>...// scr: UDP related<br>          }<br>            switch (transmit(c)) {<br>            case TRANSMIT_COMPLETE:<br>                if (c-&gt;state == conn_mwrite) { // scr: ---------&gt; a)<br>                    conn_release_items(c);<br>                    /* XXX:  I don&#39;t know why this wasn&#39;t the general case */<br>                    if(c-&gt;protocol == binary_prot) {<br>                        conn_set_state(c, c-&gt;write_and_go);<br>                    } else {<br>                        conn_set_state(c, conn_new_cmd);<br>                    }<br>                } else if (c-&gt;state == conn_write) {<br>...// scr: not applicable<br>                } else {<br>...// scr: not applicable<br>                }<br>                break;<br><br>            case TRANSMIT_INCOMPLETE: // scr: ------------------&gt; b)<br>            case TRANSMIT_HARD_ERROR:<br>                break;                   /* Continue in state machine. */<br><br>            case TRANSMIT_SOFT_ERROR: // scr: ------------------&gt; c)<br>                stop = true;<br>                break;<br>            }<br>            break;<br>...</pre><p>According to the result of transmit, the logic flows to the following 3 branches,</p><p>a) If the result is TRANSMIT_COMPLETE, 1) finalise the current command processing with <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#Finish-read">conn_release_items</a>; 2) switch the state to <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#conn-new-cmd">conn_new_cmd</a> which 3) eventually falls to conn_waiting and, <a href="https://holmeshe.me/understanding-memcached-source-code-VIII/#conn-waiting">as discussed</a>, finishes the current <em>event loop</em>.</p><p>b) If the result is TRANSMIT_INCOMPLETE and TRANSMIT_HARD_ERROR, the <strong>state machine</strong> keeps the same <strong>state</strong>, and the subsequent passes through the <em>event loop</em> continues consuming more data in msglist. Unlike read operation, TRANSMIT_INCOMPLETE does not lead to immediate <em>event loop</em> finish because write operation does not block until buffer is full.</p><p>c) TRANSMIT_SOFT_ERROR means the buffer is full, hence finish the current <em>event loop</em> iteration straight away.</p><h4>Finish read</h4><pre>static void conn_release_items(conn *c) {<br>    assert(c != NULL);<br><br>    if (c-&gt;item) {<br>...// scr: not applicable<br>    }<br><br>    while (c-&gt;ileft &gt; 0) {<br>        item *it = *(c-&gt;icurr);<br>        assert((it-&gt;it_flags &amp; ITEM_SLABBED) == 0);<br>        item_remove(it); // scr: ---------------------&gt; 1)<br>        c-&gt;icurr++;<br>        c-&gt;ileft--;<br>    }<br><br>...// scr: cas<br><br>    c-&gt;icurr = c-&gt;ilist;<br>...// scr: cas<br>}</pre><p>Not sure if you noticed or not, there is a subtle bug in the <a href="https://holmeshe.me/understanding-memcached-source-code-VI/#Read">LRU III</a>, the <em>reference count</em> of the <strong>item</strong> in <a href="https://holmeshe.me/understanding-memcached-source-code-VI/#Read">read</a> operation is not returned to 0 as in other operations. This is because</p><p>1) all <strong>item</strong>s ownership are batched released here at the end the (read) command processing.</p><p><em>Originally published at </em><a href="https://holmeshe.me/understanding-memcached-source-code-VIII/"><em>holmeshe.me</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=8d6249d62943" width="1" height="1" alt=""><hr><p><a href="https://medium.com/source-code/understanding-the-memcached-source-code-event-driven-ii-8d6249d62943">Understanding The Memcached Source Code-Event Driven II</a> was originally published in <a href="https://medium.com/source-code">source code</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Understanding The Memcached Source Code — Event Driven I]]></title>
            <link>https://medium.com/source-code/understanding-the-memcached-source-code-event-driven-i-cd6c947c4092?source=rss-63f89bf0f9b4------2</link>
            <guid isPermaLink="false">https://medium.com/p/cd6c947c4092</guid>
            <category><![CDATA[memcached]]></category>
            <category><![CDATA[open-source]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[english-posts]]></category>
            <dc:creator><![CDATA[Holmes He]]></dc:creator>
            <pubDate>Sun, 27 Jan 2019 04:05:32 GMT</pubDate>
            <atom:updated>2019-06-02T00:07:56.975Z</atom:updated>
            <cc:license>https://creativecommons.org/licenses/by-nd/4.0/</cc:license>
            <content:encoded><![CDATA[<h3>Understanding The Memcached Source Code — Event Driven I</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*a_UyoyORTBjouCiygeBpDg.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/photos/0UQJiRQVzsw?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">NeONBRAND</a> on <a href="https://unsplash.com/search/photos/cake?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a></figcaption></figure><blockquote>Slab allocator is the core module of the cache system, which largely determines how efficient the bottleneck resource, memory, can be utilised. The other 3 parts, namely, LRU algorithm for entry expiration; and an event driven model based on libevent; and the consistent harsh for data distribution, are built around it.</blockquote><p><a href="https://medium.com/source-code/understanding-the-memcached-source-code-slab-i-9199de613762">Slab I</a><br><a href="https://medium.com/source-code/understanding-the-memcached-source-code-slab-ii-6477c0482548">Slab II</a><br><a href="https://medium.com/source-code/https-medium-com-source-code-understanding-the-memcached-source-code-slab-iii-cb06e577d73e">Slab III</a><br><a href="https://medium.com/source-code/understanding-the-memcached-source-code-lru-i-8b383c561638">LRU I</a><br><a href="https://medium.com/source-code/understanding-the-memcached-source-code-lru-ii-ea4067863652">LRU II</a><br><a href="https://medium.com/source-code/understanding-the-memcached-source-code-lru-iii-87d1c7497cb9">LRU III</a><br>Event driven I (this article)</p><p>In classic <em>multithreading</em>, large amounts of slow and blocking operations, mostly, I/O, can easily drain out available thread resources, which severely constrains the maximum number of requests a server can handle per unit time. More specific, threads are scheduled out and put into sleep in the middle of procedures that contain blocking I/O, despite piling up requests packets queuing within the network stack. In such situation, server side will show low throughput, low CPU saturation and high latency.</p><blockquote>Here is a <a href="https://hackernoon.com/back-end-performance-those-metrics-we-care-about-ade678e87969">post</a> around server side performance. Feel free to check it out.</blockquote><h3>An introduction to event driven</h3><p>This is where asynchronous <strong>event driven</strong> model comes in, which drops the idea that <em>context</em> of a <em>session</em> must be coupled with a thread. In such model, <em>session</em> contexts are contained within and managed by a <strong>drive machine</strong> and a thread is fully unleashed with unblocking I/O operations. More specific, 1) when I/O occurs in the middle of a procedure, a thread does not block but instantly switch to the processing of another <em>request</em>; and 2) when the I/O completes, the <em>context</em> will be picked up by the <strong>drive machine</strong> to resume the interrupted <em>session</em>. As such, a potentially slow procedure is effectively divided into multiple manageable pieces, and the cutting points are marked by I/O operations. This results in more performant single threaded architecture in comparison to those employ thousands of threads.</p><blockquote>In my understanding, <strong>event driven</strong> model, in its essential, is yet another instance of “divide and conquer” and “trade space for time” in a not very obvious way.</blockquote><p>On the other hand, <em>multithreading</em> can be still used in <strong>event driven</strong> model purely for the purpose of parallelism. Thus, in practice, the number of threads employed does not exceed that of CPU cores. I will discuss the <strong>Memcached</strong> <em>multithreading</em> soon in <a href="https://holmeshe.me/understanding-memcached-source-code-VII/#Thread-model">thread model</a>.</p><h3>The drive machine</h3><p>From a developer’s point of view, there are numerous ways to program an asynchronous <strong>even driven</strong> server. <strong>Memcached</strong> adopts an approach called <em>state machine</em>, in which logic flow is divided into non-linear fragments identified with <strong>state</strong>s, which is normally controlled by a huge switch case. The bright-side of this approach is that the mentioned breakdown of slow procedure is sincerely reflected by the logic fragments. But it makes the code style a bit different from what most developers are already used to.</p><p>Following is how the event <strong>drive</strong>n state<strong> machine</strong> actually looks like.</p><pre>static void drive_machine(conn *c) {<br>    bool stop = false;<br>    int sfd;<br>    socklen_t addrlen;<br>    struct sockaddr_storage addr;<br>    int nreqs = settings.reqs_per_event;<br>    int res;<br>    const char *str;<br>...<br><br>    assert(c != NULL);<br><br>    while (!stop) {<br><br>        switch(c-&gt;state) {<br>        case conn_listening:<br>            addrlen = sizeof(addr);<br>...<br>            sfd = accept(c-&gt;sfd, (struct sockaddr *)&amp;addr, &amp;addrlen);<br>...<br>            if (sfd == -1) {<br>...<br>            }<br>...<br><br>            if (settings.maxconns_fast &amp;&amp;<br>                stats_state.curr_conns + stats_state.reserved_fds &gt;= settings.maxconns - 1) {<br>...<br>            } else {<br>                dispatch_conn_new(sfd, conn_new_cmd, EV_READ | EV_PERSIST,<br>                                     DATA_BUFFER_SIZE, c-&gt;transport);<br>            }<br><br>            stop = true;<br>            break;<br><br>        case conn_waiting:<br>...<br>            stop = true;<br>            break;<br><br>        case conn_read:<br>...<br>            break;<br><br>        case conn_parse_cmd :<br>...<br>            break;<br><br>        case conn_new_cmd:<br>...<br>            break;<br><br>        case conn_nread:<br>...<br>            break;<br>        case conn_swallow:<br>...<br>            break;<br>        case conn_write:<br>...<br>        case conn_mwrite:<br>...<br>            break;<br>        case conn_closing:<br>            if (IS_UDP(c-&gt;transport))<br>                conn_cleanup(c);<br>            else<br>                conn_close(c);<br>            stop = true;<br>            break;<br><br>        case conn_closed:<br>            /* This only happens if dormando is an idiot. */<br>            abort();<br>            break;<br><br>        case conn_watch:<br>            /* We handed off our connection to the logger thread. */<br>            stop = true;<br>            break;<br>        case conn_max_state:<br>            assert(false);<br>            break;<br>        }<br>    }<br><br>    return;<br>}</pre><p>The omitted switch blocks will be discussed in detail in following posts, so no worries.</p><h3>Thread model</h3><p>The thread model of <strong>Memcached</strong> is quite standard. There is a <em>dispatcher thread</em>, and there are preconfigured number of <em>worker thread</em>s. Each thread runs an independent <strong>drive machine</strong> described above. The <em>dispatcher thread</em>, of which the responsible is to distribute <em>request</em>s among <em>worker thread</em>s, only executes code under conn_listening. The actual requests are completed by <em>worker thread</em>s running on the rest of the <strong>state</strong>s.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/484/0*1gallSpvxfseMzWd.png" /></figure><p>Next we go through the bootstrap portion of main function which establishes the various building blocks of <strong>event driven</strong> as well as the <em>multithreading</em> mechanism. And we will also see locations of the discussed sub-system ***_init methods in relation to the whole initialization process.</p><p>First thing first, all the <em>system initialization</em> relevant procedures are executed in the discussed <em>dispatcher thread</em>.</p><p>The call stack of this process is</p><pre>|-main<br>  |-hash_init          (LRU II)<br>  |-assoc_init         (LRU II)<br>  |-conn_init<br>  |-slabs_init         (Slab I)<br>  |-memcached_thread_init<br>    |-setup_thread<br>    |-create_worker<br>  |-server_sockets<br>    |-new_socket<br>    |-conn_new</pre><h3>System initialization</h3><pre>int main (int argc, char **argv) {<br>...// scr: ---------------------------------------------------&gt; *)<br>...// scr: initialize `settings` using default values and command line arguements<br>...// scr: sanity check<br><br>    if (hash_init(hash_type) != 0) { // scr: -------------&gt; LRU II<br>        fprintf(stderr, &quot;Failed to initialize hash_algorithm!\n&quot;);<br>        exit(EX_USAGE);<br>    }<br><br>...// scr: initialize `settings` &amp; sanity check<br><br>    if (maxcore != 0) { // scr: ------------------------------&gt; 1)<br>        struct rlimit rlim_new;<br>        /*<br>         * First try raising to infinity; if that fails, try bringing<br>         * the soft limit to the hard.<br>         */<br>        if (getrlimit(RLIMIT_CORE, &amp;rlim) == 0) {<br>            rlim_new.rlim_cur = rlim_new.rlim_max = RLIM_INFINITY;<br>            if (setrlimit(RLIMIT_CORE, &amp;rlim_new)!= 0) {<br>                /* failed. try raising just to the old max */<br>                rlim_new.rlim_cur = rlim_new.rlim_max = rlim.rlim_max;<br>                (void)setrlimit(RLIMIT_CORE, &amp;rlim_new);<br>            }<br>        }<br>        /*<br>         * getrlimit again to see what we ended up with. Only fail if<br>         * the soft limit ends up 0, because then no core files will be<br>         * created at all.<br>         */<br><br>        if ((getrlimit(RLIMIT_CORE, &amp;rlim) != 0) || rlim.rlim_cur == 0) {<br>            fprintf(stderr, &quot;failed to ensure corefile creation\n&quot;);<br>            exit(EX_OSERR);<br>        }<br>    }<br><br>    if (getrlimit(RLIMIT_NOFILE, &amp;rlim) != 0) { // scr: ------&gt; 1)<br>        fprintf(stderr, &quot;failed to getrlimit number of files\n&quot;);<br>        exit(EX_OSERR);<br>    } else {<br>        rlim.rlim_cur = settings.maxconns;<br>        rlim.rlim_max = settings.maxconns;<br>        if (setrlimit(RLIMIT_NOFILE, &amp;rlim) != 0) {<br>            fprintf(stderr, &quot;failed to set rlimit for open files. Try starting as root or requesting smaller maxconns value.\n&quot;);<br>            exit(EX_OSERR);<br>        }<br>    }<br><br>...// scr: ---------------------------------------------------&gt; *)<br><br>    main_base = event_init(); // scr: ------------------------&gt; 2)<br>...// scr: stat<br>    assoc_init(settings.hashpower_init); // scr: ---------&gt; LRU II<br>    conn_init(); // scr: -------------------------------------&gt; 3)<br>    slabs_init(settings.maxbytes, settings.factor, preallocate,<br>            use_slab_sizes ? slab_sizes : NULL); // scr: -&gt; Slab I<br>...<br>    memcached_thread_init(settings.num_threads, main_base); //scr:4)<br><br>...// scr: maintainer threads initialization<br>...// scr: unix socket<br><br>    /* create the listening socket, bind it, and init */<br>    if (settings.socketpath == NULL) {<br>...// scr: not applicable<br>        if (portnumber_filename != NULL) {<br>...// scr: not applicable<br>        }<br><br>        errno = 0; // scr: -----------------------------------&gt; 5)<br>        if (settings.port &amp;&amp; server_sockets(settings.port, tcp_transport,<br>                                           portnumber_file)) {<br>            vperror(&quot;failed to listen on TCP port %d&quot;, settings.port);<br>            exit(EX_OSERR);<br>        }<br><br>        errno = 0; // scr: -----------------------------------&gt; 5)<br>        if (settings.udpport &amp;&amp; server_sockets(settings.udpport, udp_transport,<br>                                              portnumber_file)) {<br>            vperror(&quot;failed to listen on UDP port %d&quot;, settings.udpport);<br>            exit(EX_OSERR);<br>        }<br>        if (portnumber_file) {<br>...// scr: not applicable<br>        }<br><br>    usleep(1000);<br>...<br>    if (event_base_loop(main_base, 0) != 0) { // scr: --------&gt; 6)<br>        retval = EXIT_FAILURE;<br>    }<br><br>...// scr: finalization<br>}</pre><p>The two relevant steps are 4) and 5) which will be discussed in the following sections.</p><p>1) Raise the limit for core dump file size as well as the number of file descriptors.</p><p>2) Call <a href="http://www.wangafu.net/~nickm/libevent-2.1/doxygen/html/event__compat_8h.html#aa72d84e78eb6f08dc580e6245c087cb6">event_init</a> to initialize the <strong>libevent</strong> framework. The value returned is called an <em>event base</em>.</p><p>3) For all potential connections, call conn_init to allocate space to store their respective <em>context</em>s (located using file descriptor in global variable conns). The role of <em>context</em> in <strong>event driven</strong> model has already been discussed in <a href="https://holmeshe.me/understanding-memcached-source-code-VII/#An-introduction-to-event-driven">introduction</a>.</p><p>4) Preallocate threads and their associated resources using <a href="https://holmeshe.me/understanding-memcached-source-code-VII/#memcached-thread-init">memcached_thread_init</a>.</p><p>5) Setup the socket and first event listener — conn_listening.</p><p>6) Call <a href="http://www.wangafu.net/~nickm/libevent-2.1/doxygen/html/event_8h.html#a76e311cff042dab77125e309315a0617">event_base_loop</a> to start the <strong>event loop</strong>.</p><p>*) Other miscellaneous system operations, such as setting the signal handler for SIGINT and SIGTERM; setbuf stderr to NULL; dropping the root privileges of the process; and daemonizing. If those names do not ring a bell, &lt;&lt;Advanced UNIX Programming&gt;&gt; is your friend.</p><h3>Threads initialization</h3><p>The core data structure of <em>multithreading</em> mechanism is</p><pre>typedef struct {<br>    pthread_t thread_id;        /* unique ID of this thread */<br>    struct event_base *base;    /* libevent handle this thread uses */<br>    struct event notify_event;  /* listen event for notify pipe */<br>    int notify_receive_fd;      /* receiving end of notify pipe */<br>    int notify_send_fd;         /* sending end of notify pipe */<br>...// scr: stat<br>    struct conn_queue *new_conn_queue; /* queue of new connections to handle */<br>...// scr: cas &amp; log<br>} LIBEVENT_THREAD;</pre><h4>memcached_thread_init</h4><pre>void memcached_thread_init(int nthreads, struct event_base *main_base) {<br>...// scr: initialize all sorts of mutexes and condition variables<br><br>    threads = calloc(nthreads, sizeof(LIBEVENT_THREAD)); // scr 1)<br>    if (! threads) {<br>        perror(&quot;Can&#39;t allocate thread descriptors&quot;);<br>        exit(1);<br>    }<br><br>    dispatcher_thread.base = main_base; // scr: --------------&gt; 2)<br>    dispatcher_thread.thread_id = pthread_self(); // scr: ----&gt; 3)<br><br>    for (i = 0; i &lt; nthreads; i++) {<br>        int fds[2];<br>        if (pipe(fds)) { // scr: -----------------------------&gt; 4)<br>            perror(&quot;Can&#39;t create notify pipe&quot;);<br>            exit(1);<br>        }<br><br>        threads[i].notify_receive_fd = fds[0]; // scr: -------&gt; 4)<br>        threads[i].notify_send_fd = fds[1]; // scr: ----------&gt; 4)<br><br>        setup_thread(&amp;threads[i]); // scr: -------------------&gt; 5)<br>        /* Reserve three fds for the libevent base, and two for the pipe */<br>        stats_state.reserved_fds += 5;<br>    }<br><br>    /* Create threads after we&#39;ve done all the libevent setup. */<br>    for (i = 0; i &lt; nthreads; i++) {<br>        create_worker(worker_libevent, &amp;threads[i]); // scr: -&gt; 6)<br>    }<br><br>    /* Wait for all the threads to set themselves up before returning. */<br>    pthread_mutex_lock(&amp;init_lock);<br>    wait_for_thread_registration(nthreads);<br>    pthread_mutex_unlock(&amp;init_lock);<br>}</pre><p>1) Allocate memory for an array of <a href="https://holmeshe.me/understanding-memcached-source-code-VII/#Threads-initialization">LIBEVENT_THREAD</a>. The number of thread is num_threads Each element represents one thread. As described above, better the num_threads does not exceed the number of cores.</p><p>2) Set the <em>event base</em> for the dispatcher_thread which represents the main thread itself. Note that dispatcher_thread is a global variable so the reference is accessible to all the <em>worker thread</em>s.</p><p>3) Set the thread id for dispatcher_thread.</p><p>4) Initialize the <a href="http://man7.org/linux/man-pages/man2/pipe.2.html">pipe</a> fds for each of the <em>worker thread</em>. Here the notify_send_fd is used for communication between <em>dispatcher thread</em> and <em>worker thread</em>s - whenever the <em>dispatcher thread</em> <a href="http://man7.org/linux/man-pages/man2/write.2.html">write</a>s to notify_send_fd, an <strong>event</strong> is generated on the other side, notify_receive_fd, which is listened by <em>worker thread</em>s. Again, &lt;&lt;Advanced UNIX Programming&gt;&gt; gives more information about pipe.</p><p>5) The full method name is supposed to be setup_libevent_for_each_thread. Will examine this method in the <a href="https://holmeshe.me/understanding-memcached-source-code-VII/#setup-thread">next section</a>.</p><p>6) Call pthread_create to create the actual <em>worker threads</em>. Will examine this method in <a href="https://holmeshe.me/understanding-memcached-source-code-VII/#create-worker">create_worker</a>.</p><h4>setup_thread</h4><pre>static void setup_thread(LIBEVENT_THREAD *me) {<br>    me-&gt;base = event_init(); // scr: -------------------------&gt; 1)<br>    if (! me-&gt;base) {<br>        fprintf(stderr, &quot;Can&#39;t allocate event base\n&quot;);<br>        exit(1);<br>    }<br><br>    /* Listen for notifications from other threads */<br>    event_set(&amp;me-&gt;notify_event, me-&gt;notify_receive_fd, // scr: 2)<br>              EV_READ | EV_PERSIST, thread_libevent_process, me);<br>    event_base_set(me-&gt;base, &amp;me-&gt;notify_event); // scr: -------&gt; 2)<br><br>    if (event_add(&amp;me-&gt;notify_event, 0) == -1) { // scr: -----&gt; 2)<br>        fprintf(stderr, &quot;Can&#39;t monitor libevent notify pipe\n&quot;);<br>        exit(1);<br>    }<br><br>    me-&gt;new_conn_queue = malloc(sizeof(struct conn_queue)); //  3)<br>    if (me-&gt;new_conn_queue == NULL) {<br>        perror(&quot;Failed to allocate memory for connection queue&quot;);<br>        exit(EXIT_FAILURE);<br>    }<br>    cq_init(me-&gt;new_conn_queue);<br><br>...// scr: stat &amp; cas<br>}</pre><p>1) Call <a href="http://www.wangafu.net/~nickm/libevent-2.1/doxygen/html/event__compat_8h.html#aa72d84e78eb6f08dc580e6245c087cb6">event_init</a> to initialize the <strong>libevent</strong> instance for the <em>worker thread</em>. As discussed in <a href="https://holmeshe.me/understanding-memcached-source-code-VII/#Thread-model">thread model</a>, each <em>worker thread</em> runs its own <strong>drive machine</strong>.</p><p>2) Set the thread_libevent_process as the callback of events emitted from the discussed notify_receive_fd. The major function of thread_libevent_process is to link the actual <strong>drive machine</strong> to <strong>event</strong>s, which we will see very soon in <a href="https://holmeshe.me/understanding-memcached-source-code-VII/#thread-libevent-process">inter-thread communication</a>.</p><p>3) Allocate and initialize the connection queue of the <em>worker thread</em>.</p><h4>create_worker</h4><pre>static void create_worker(void *(*func)(void *), void *arg) {<br>    pthread_attr_t  attr;<br>    int             ret;<br><br>    pthread_attr_init(&amp;attr);<br><br>    if ((ret = pthread_create(&amp;((LIBEVENT_THREAD*)arg)-&gt;thread_id, &amp;attr, func, arg)) != 0) {<br>        fprintf(stderr, &quot;Can&#39;t create thread: %s\n&quot;,<br>                strerror(ret));<br>        exit(1);<br>    }<br>}</pre><p>As mentioned, this method calls <a href="http://man7.org/linux/man-pages/man3/pthread_create.3.html">pthread_create</a> to create the actual <em>worker thread</em>s. The callback passed through is worker_libevent which essentially starts the <strong>event loop</strong> using <a href="http://www.wangafu.net/~nickm/libevent-2.1/doxygen/html/event_8h.html#a76e311cff042dab77125e309315a0617">event_base_loop</a>, this time, on <em>worker thread</em>s rather than <em>dispatch thread</em>.</p><h3>Socket initialization</h3><p>The methods involved in socket initialization reconcile the initialization of both <em>TCP</em> and <em>UDP</em> while the following discussion covers only the <em>TCP</em> logic branch. And we consider portnumber_file is not set so as to focus on the critical path.</p><p>Unlike <em>worker thread</em>s that listen to internal (<a href="http://man7.org/linux/man-pages/man2/pipe.2.html">pipe</a>) fds, <em>dispatch thread</em> is responsible for <strong>event</strong>s generated from external socket fds (by network requests). The method that initializes sockets is server_sockets.</p><p>If network interface is not indicated by inter, server_sockets is equivalent to</p><h4>server_socket</h4><pre>static int server_socket(const char *interface,<br>                         int port,<br>                         enum network_transport transport,<br>                         FILE *portnumber_file) {<br>    int sfd;<br>    struct linger ling = {0, 0};<br>    struct addrinfo *ai;<br>    struct addrinfo *next;<br>    struct addrinfo hints = { .ai_flags = AI_PASSIVE,<br>                              .ai_family = AF_UNSPEC };<br>    char port_buf[NI_MAXSERV];<br>    int error;<br>    int success = 0;<br>    int flags =1;<br><br>    hints.ai_socktype = IS_UDP(transport) ? SOCK_DGRAM : SOCK_STREAM;<br><br>    if (port == -1) {<br>        port = 0;<br>    }<br>    snprintf(port_buf, sizeof(port_buf), &quot;%d&quot;, port);<br>    error= getaddrinfo(interface, port_buf, &amp;hints, &amp;ai); //scr 1)<br>    if (error != 0) {<br>...// scr: error handling<br>    }<br><br>    for (next= ai; next; next= next-&gt;ai_next) { // scr: ------&gt; 2)<br>        conn *listen_conn_add;<br>        if ((sfd = new_socket(next)) == -1) { // scr: --------&gt; 3)<br>            /* getaddrinfo can return &quot;junk&quot; addresses,<br>             * we make sure at least one works before erroring.<br>             */<br>            if (errno == EMFILE) {<br>                /* ...unless we&#39;re out of fds */<br>                perror(&quot;server_socket&quot;);<br>                exit(EX_OSERR);<br>            }<br>            continue;<br>        }<br>// scr: ------------------------------------------------------&gt; 4)<br>        setsockopt(sfd, SOL_SOCKET, SO_REUSEADDR, (void *)&amp;flags, sizeof(flags));<br>        if (IS_UDP(transport)) {<br>...// scr: not applicable<br>        } else {<br>            error = setsockopt(sfd, SOL_SOCKET, SO_KEEPALIVE, (void *)&amp;flags, sizeof(flags));<br>            if (error != 0)<br>                perror(&quot;setsockopt&quot;);<br><br>            error = setsockopt(sfd, SOL_SOCKET, SO_LINGER, (void *)&amp;ling, sizeof(ling));<br>            if (error != 0)<br>                perror(&quot;setsockopt&quot;);<br><br>            error = setsockopt(sfd, IPPROTO_TCP, TCP_NODELAY, (void *)&amp;flags, sizeof(flags));<br>            if (error != 0)<br>                perror(&quot;setsockopt&quot;);<br>        }<br>// scr: ------------------------------------------------------&gt; 5)<br>        if (bind(sfd, next-&gt;ai_addr, next-&gt;ai_addrlen) == -1) {<br>...// scr: error handling<br>        } else {<br>            success++;<br>            if (!IS_UDP(transport) &amp;&amp; listen(sfd, settings.backlog) == -1) {<br>...// scr: error handling<br>            }<br>            if (portnumber_file != NULL &amp;&amp;<br>...// scr: not applicable<br>            }<br>        }<br><br>        if (IS_UDP(transport)) {<br>...// scr: not applicable<br>        } else { // scr: -------------------------------------&gt; 6)<br>            if (!(listen_conn_add = conn_new(sfd, conn_listening,<br>                                             EV_READ | EV_PERSIST, 1,<br>                                             transport, main_base))) {<br>                fprintf(stderr, &quot;failed to create listening connection\n&quot;);<br>                exit(EXIT_FAILURE);<br>            }<br>            listen_conn_add-&gt;next = listen_conn; // scr: -----&gt; 7)<br>            listen_conn = listen_conn_add;<br>        }<br>    }<br><br>    freeaddrinfo(ai);<br><br>    /* Return zero iff we detected no errors in starting up connections */<br>    return success == 0;<br>}</pre><p>1) Get all the available network interfaces.</p><p>2) Iterate all the network interfaces and setup the sockets with the following steps.</p><p>3) new_socket encapsulates the operation of <a href="http://man7.org/linux/man-pages/man2/socket.2.html">socket</a> creation as well as that of setting it to non-block.</p><p>4) Tweak the newly created <a href="http://man7.org/linux/man-pages/man7/socket.7.html">socket</a> fd using <a href="http://man7.org/linux/man-pages/man2/setsockopt.2.html">setsockopt</a>, in which</p><p>SO_REUSEADDR allows binding to a port in TIME_WAIT. This is useful for instantly rebooting a server on a “not fresh” TCP port;</p><p>SO_KEEPALIVE sends heartbeats to detect an absent client, and to release the resource for network connection in both kernel and user space; <a href="https://holmeshe.me/network-essentials-setsockopt-SO_KEEPALIVE/">learn more</a></p><p>SO_LINGER enables fast close of a connection on RST; <a href="http://deepix.github.io/2016/10/21/tcprst.html">learn more</a></p><p>TCP_NODELAY disables <em>nagle</em> to improve latency. <a href="https://holmeshe.me/network-essentials-setsockopt-TCP_NODELAY/">learn more</a></p><p>5) <a href="http://man7.org/linux/man-pages/man2/bind.2.html">bind</a> and start <a href="http://man7.org/linux/man-pages/man2/listen.2.html">listen</a>ing to the fd.</p><p>6) conn_new initializes the <em>context</em> for the fd and adds it to <strong>libevent</strong> with initial <strong>state</strong> set to conn_listening and callback as event_handler. Here event_handler is another transient method leading to the <strong>drive machine</strong> on <em>dispatcher thread</em>. Likewise, this method will be discussed soon in <a href="https://holmeshe.me/understanding-memcached-source-code-VII/#event-handler">inter-thread communication</a>.</p><pre>conn *conn_new(const int sfd, enum conn_states init_state,<br>                const int event_flags,<br>                const int read_buffer_size, enum network_transport transport,<br>                struct event_base *base) {<br>    conn *c;<br>...// scr: initialize context conn<br>    c-&gt;state = init_state;<br>...// scr: initialize context conn<br><br>    event_set(&amp;c-&gt;event, sfd, event_flags, event_handler, (void *)c);<br>    event_base_set(base, &amp;c-&gt;event);<br>    c-&gt;ev_flags = event_flags;<br><br>    if (event_add(&amp;c-&gt;event, 0) == -1) {<br>        perror(&quot;event_add&quot;);<br>        return NULL;<br>    }<br>...// scr: stat<br>    return c;<br>}</pre><p>7) Add the <em>context</em> to the head of a global list listen_conn.</p><p>Next we briefly go through the process that handles a new connection to wrap up the</p><h3>Inter-thread communication</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/513/0*NT2hSGtxQC0Q9vES.png" /></figure><h4>event_handler</h4><p>Firstly, after a TCP connection completes, the fd monitored by <em>dispatcher thread</em> notifies <strong>libevent</strong>, which invokes the mentioned event_handler. Next, the logic flow enters the code snippet we got in the beginning - the <strong>drive machine</strong>, with <em>context</em> <strong>state</strong> initialized as conn_listening in <a href="https://holmeshe.me/understanding-memcached-source-code-VII/#Socket-initialization">socket initialization</a>.</p><pre>static void drive_machine(conn *c) {<br>...<br>    while (!stop) {<br><br>        switch(c-&gt;state) {<br>        case conn_listening:<br>            addrlen = sizeof(addr);<br>...<br>                  // scr: ------------------------------------&gt; 1)<br>            sfd = accept(c-&gt;sfd, (struct sockaddr *)&amp;addr, &amp;addrlen);<br>...<br>            if (sfd == -1) {<br>...// scr: error handling<br>            }<br>...<br><br>            if (settings.maxconns_fast &amp;&amp;<br>                stats_state.curr_conns + stats_state.reserved_fds &gt;= settings.maxconns - 1) {<br>...// scr: error handling<br>            } else {<br>                // scr: --------------------------------------&gt; 2)<br>                dispatch_conn_new(sfd, conn_new_cmd, EV_READ | EV_PERSIST,<br>                                     DATA_BUFFER_SIZE, c-&gt;transport);<br>            }<br><br>            stop = true;<br>            break;<br>...<br>            break;<br>        }<br>    }<br><br>    return;<br>}</pre><p>At this stage, the <strong>drive machine</strong> 1) <a href="http://man7.org/linux/man-pages/man2/accept.2.html">accept</a>s the connection and derives another fd that can be <a href="http://man7.org/linux/man-pages/man2/read.2.html">read</a> from. It 2) then calls dispatch_conn_new with the new fd and other relevant information including the next <strong>state</strong>, conn_new_cmd.</p><h4>dispatch_conn_new</h4><pre>void dispatch_conn_new(int sfd, enum conn_states init_state, int event_flags,<br>                       int read_buffer_size, enum network_transport transport) {<br>    CQ_ITEM *item = cqi_new();<br>    char buf[1];<br>    if (item == NULL) {<br>...// scr: error handling<br>    }<br><br>    int tid = (last_thread + 1) % settings.num_threads; // scr: 1)<br><br>    LIBEVENT_THREAD *thread = threads + tid; // scr: ---------&gt; 1)<br><br>    last_thread = tid; // scr: -------------------------------&gt; 1)<br><br>    item-&gt;sfd = sfd; // scr: ---------------------------------&gt; 2)<br>    item-&gt;init_state = init_state;<br>    item-&gt;event_flags = event_flags;<br>    item-&gt;read_buffer_size = read_buffer_size;<br>    item-&gt;transport = transport;<br><br>    cq_push(thread-&gt;new_conn_queue, item); // scr: -----------&gt; 3)<br><br>    MEMCACHED_CONN_DISPATCH(sfd, thread-&gt;thread_id);<br>    buf[0] = &#39;c&#39;;<br>    if (write(thread-&gt;notify_send_fd, buf, 1) != 1) { // scr: &gt; 4)<br>        perror(&quot;Writing to thread notify pipe&quot;);<br>    }<br>}</pre><p>1) Round robin the threads established in <a href="https://holmeshe.me/understanding-memcached-source-code-VII/#Threads-initialization">threads initialization</a>.</p><p>2) Initializes a CQ_ITEM instance. Here CQ_ITEM is an intermediate object passed to <em>worker thread</em>s through <em>connection queue</em>, so <em>worker thread</em>s can create new <em>context</em> based on it.</p><pre>typedef struct conn_queue_item CQ_ITEM;<br>struct conn_queue_item {<br>    int               sfd;<br>    enum conn_states  init_state;<br>    int               event_flags;<br>    int               read_buffer_size;<br>    enum network_transport     transport;<br>    CQ_ITEM          *next;<br>};</pre><p>3) Push CQ_ITEM to the <em>connection queue</em>.</p><p>4) Write to notify_send_fd with the command &#39;c&#39;.</p><p>As discussed <a href="https://holmeshe.me/understanding-memcached-source-code-VII/#memcached-thread-init">before</a>, 4) generates an <strong>event</strong> on the other side of the <a href="http://man7.org/linux/man-pages/man2/pipe.2.html">pipe</a> (on the chosen <em>worker thread</em>), which invokes</p><h4>thread_libevent_process</h4><pre>static void thread_libevent_process(int fd, short which, void *arg) {<br>    LIBEVENT_THREAD *me = arg;<br>    CQ_ITEM *item;<br>    char buf[1];<br>    unsigned int timeout_fd;<br><br>    if (read(fd, buf, 1) != 1) { // scr: ---------------------&gt; 1)<br>        if (settings.verbose &gt; 0)<br>            fprintf(stderr, &quot;Can&#39;t read from libevent pipe\n&quot;);<br>        return;<br>    }<br><br>    switch (buf[0]) {<br>    case &#39;c&#39;:<br>        item = cq_pop(me-&gt;new_conn_queue); // scr: -----------&gt; 2)<br><br>        if (NULL != item) {<br>            conn *c = conn_new(item-&gt;sfd, item-&gt;init_state, item-&gt;event_flags,<br>                               item-&gt;read_buffer_size, item-&gt;transport,<br>                               me-&gt;base); // scr: ------------&gt; 3)<br>            if (c == NULL) {<br>...// scr: error handling<br>            } else {<br>                c-&gt;thread = me; // scr: ----------------------&gt; 4)<br>            }<br>            cqi_free(item);<br>        }<br>        break;<br>    /* we were told to pause and report in */<br>...// scr: not applicable<br>        break;<br>    }<br>}</pre><p>1) Read the command (i.e., &#39;c&#39;) from the <a href="http://man7.org/linux/man-pages/man2/pipe.2.html">pipe</a>.</p><p>2) Read the CQ_ITEM from the <em>connection queue</em>.</p><p>3) Call conn_new. In <a href="https://holmeshe.me/understanding-memcached-source-code-VII/#server-socket">server_socket</a> we know that conn_new establishes the <em>context</em>, this time, for the new connection, and adds the <a href="http://man7.org/linux/man-pages/man2/accept.2.html">accept</a>ed fd to <strong>libevent</strong>. Here on <em>worker thread</em>, the callback is set to event_handler, which essentially connects the <strong>drive machine</strong> to the upcoming <strong>event</strong>s on the same connection.</p><p>4) Set the <a href="https://holmeshe.me/understanding-memcached-source-code-VII/#Threads-initialization">thread information</a> to the context.</p><h3>Reference</h3><p>W. Richard Stevens. 1992. Advanced Programming in the UNIX Environment. Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA.</p><p><a href="http://deepix.github.io/2016/10/21/tcprst.html">Resetting a TCP connection and SO_LINGER</a></p><p><a href="https://www.usenix.org/legacy/publications/library/proceedings/usenix99/full_papers/pai/pai_html/node7.html">Single-process event-driven</a></p><p><em>Originally published at </em><a href="https://holmeshe.me/understanding-memcached-source-code-VII/"><em>holmeshe.me</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=cd6c947c4092" width="1" height="1" alt=""><hr><p><a href="https://medium.com/source-code/understanding-the-memcached-source-code-event-driven-i-cd6c947c4092">Understanding The Memcached Source Code — Event Driven I</a> was originally published in <a href="https://medium.com/source-code">source code</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Understanding The Memcached Source Code — LRU III]]></title>
            <link>https://medium.com/source-code/understanding-the-memcached-source-code-lru-iii-87d1c7497cb9?source=rss-63f89bf0f9b4------2</link>
            <guid isPermaLink="false">https://medium.com/p/87d1c7497cb9</guid>
            <category><![CDATA[english-posts]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[open-source]]></category>
            <category><![CDATA[memcached]]></category>
            <category><![CDATA[code-analytic]]></category>
            <dc:creator><![CDATA[Holmes He]]></dc:creator>
            <pubDate>Thu, 10 Jan 2019 11:24:24 GMT</pubDate>
            <atom:updated>2019-06-02T00:07:35.623Z</atom:updated>
            <cc:license>https://creativecommons.org/licenses/by-nd/4.0/</cc:license>
            <content:encoded><![CDATA[<h3>Understanding The Memcached Source Code — LRU III</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*2-hljsWmGuaLyP37objX6g.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/photos/rXB9YjOQX8I?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Velizar Ivanov</a> on <a href="https://unsplash.com/search/photos/cake?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a></figcaption></figure><blockquote>Slab allocator is the core module of the cache system, which largely determines how efficient the bottleneck resource, memory, can be utilised. The other 3 parts, namely, LRU algorithm for entry expiration; and an event driven model based on libevent; and the consistent harsh for data distribution, are built around it.</blockquote><p><a href="https://medium.com/source-code/understanding-the-memcached-source-code-slab-i-9199de613762">Slab I</a><br><a href="https://medium.com/source-code/understanding-the-memcached-source-code-slab-ii-6477c0482548">Slab II</a><br><a href="https://medium.com/source-code/https-medium-com-source-code-understanding-the-memcached-source-code-slab-iii-cb06e577d73e">Slab III</a><br><a href="https://medium.com/source-code/understanding-the-memcached-source-code-lru-i-8b383c561638">LRU I</a><br><a href="https://medium.com/source-code/understanding-the-memcached-source-code-lru-ii-ea4067863652">LRU II</a><br>LRU III (this article)<br><a href="https://medium.com/source-code/understanding-the-memcached-source-code-event-driven-i-cd6c947c4092">Event driven I</a></p><p>In previous posts, we have discussed different facets of an <strong>item</strong>, i.e., <strong>slab</strong>, <strong>hash map</strong> and <strong>LRU list</strong> as well as their associated (CRUD) methods, which build up the internal procedures and perform client requests after the corresponding commands are parsed by the <strong>drive machine</strong>. This time we will go through those procedures by issuing <em>telnet commands</em> to a <strong>Memcached</strong> instance and see how the discussed modules work together on various <strong>item</strong> operations. We will also see the whole picture of <strong>LRU list</strong>s that maintain the property of ‘least recently used’ in accordance to those operations.</p><p>On top of standard <strong>LRU</strong> algorithm, the <strong>Memcached</strong> (1.4.28) emploies 3 lists instead of just 1, i.e., hot, warm and cold, a.k.a., <a href="https://memcached.org/blog/modern-lru/">Segmented LRU</a> for each <strong>slab class</strong>. This heuristic is implemented to reduce the lock contention between <strong>item</strong> <em>bumping</em> (an <a href="http://holmeshe.me/understanding-memcached-source-code-IV/#Linked-list">action</a> that moves recently accessed <strong>item</strong> to the list head) and <strong>item</strong> read. Moreover, unlike a casual implementation (such as the one I coded), <strong>Memcached </strong>does not <em>bump</em> <strong>item</strong> right on <a href="https://holmeshe.me/understanding-memcached-source-code-VI/#opt1"><em>read action</em></a>. Rather, the <em>bumping</em> is delayed <a href="https://holmeshe.me/understanding-memcached-source-code-VI/#opt2">to other operations when the resource is in short</a>, which could reflect <strong>Memcached</strong>‘s read-first design decision.</p><blockquote><em>In normal use cases, let’s say, a social media, the volume of read requests are more than that of other operations combined by orders of magnitude, hence it’s a critical point that worth extensive optimizations, I suppose.</em></blockquote><p>We start this post by issuing an <strong>item</strong> read command to a <strong>Memcached</strong> instance.</p><pre>~telnet localhost 11211<br>Trying 127.0.0.1…<br>Connected to localhost.<br>Escape character is ‘^]’.<br>…// add some items<br>&gt; get test</pre><h3>Read</h3><p>The the normal execution of this procedure,</p><pre>ref<br>1 |~Drive machine &amp; command parser<br>    |-process_get_command<br>++    |-item_get<br>        |-assoc_find    (LRU II)<br>      |-item_update<br>        |-item_unlink_q (LRU I)<br>        |-item_link_q   (LRU I)</pre><h4>process_get_command</h4><pre>static inline void process_get_command(conn *c, token_t *tokens, size_t ntokens, bool return_cas) {<br>    char *key;<br>    size_t nkey;<br>    int i = 0;<br>    item *it;<br>    token_t *key_token = &amp;tokens[KEY_TOKEN];<br>    char *suffix;<br>    assert(c != NULL);<br><br>    do {<br>        while(key_token-&gt;length != 0) { // scr: -------------&gt; *)<br><br>            key = key_token-&gt;value;<br>            nkey = key_token-&gt;length;<br><br>            if(nkey &gt; KEY_MAX_LENGTH) {<br>                out_string(c, &quot;CLIENT_ERROR bad command line format&quot;);<br>                while (i-- &gt; 0) {<br>                    item_remove(*(c-&gt;ilist + i));<br>                }<br>                return;<br>            }<br><br>            it = item_get(key, nkey, c); // scr: ------------&gt; 1)<br>            if (settings.detail_enabled) {<br>                stats_prefix_record_get(key, nkey, NULL != it);<br>            }<br>            if (it) {<br>                if (i &gt;= c-&gt;isize) { // scr: ----------------&gt; *)<br>                    item **new_list = realloc(c-&gt;ilist, sizeof(item *) * c-&gt;isize * 2);<br>                    if (new_list) {<br>                        c-&gt;isize *= 2;<br>                        c-&gt;ilist = new_list;<br>                    } else {<br>... // scr: stat<br>                        item_remove(it);<br>                        break;<br>                    }<br>                }<br><br>                if (return_cas)<br>                {<br>... // scr: cas<br>                }<br>                else<br>                {<br>                  MEMCACHED_COMMAND_GET(c-&gt;sfd, ITEM_key(it), it-&gt;nkey,<br>                                        it-&gt;nbytes, ITEM_get_cas(it));<br>                  if (add_iov(c, &quot;VALUE &quot;, 6) != 0 || // scr: *)<br>                      add_iov(c, ITEM_key(it), it-&gt;nkey) != 0 ||<br>                      add_iov(c, ITEM_suffix(it), it-&gt;nsuffix + it-&gt;nbytes) != 0)<br>                      {<br>                          item_remove(it);<br>                          break;<br>                      }<br>                }<br><br>... // scr: verbose &amp; stat<br><br>                item_update(it); // scr: --------------------&gt; 2)<br>                *(c-&gt;ilist + i) = it;<br>                i++;<br><br>            } else {<br>... // scr: stat<br>            }<br><br>            key_token++; // scr: ----------------------------&gt; *)<br>        }<br><br>        /*<br>         * If the command string hasn&#39;t been fully processed, get the next set<br>         * of tokens.<br>         */<br>        if(key_token-&gt;value != NULL) { // scr: --------------&gt; *)<br>            ntokens = tokenize_command(key_token-&gt;value, tokens, MAX_TOKENS);<br>            key_token = tokens;<br>        }<br><br>    } while(key_token-&gt;value != NULL);<br><br>    c-&gt;icurr = c-&gt;ilist;<br>    c-&gt;ileft = i;<br>... // scr: cas &amp; verbose<br><br>    if (key_token-&gt;value != NULL || add_iov(c, &quot;END\r\n&quot;, 5) != 0<br>        || (IS_UDP(c-&gt;transport) &amp;&amp; build_udp_headers(c) != 0)) {<br>        out_of_memory(c, &quot;SERVER_ERROR out of memory writing get response&quot;);<br>    }<br>    else { // scr: ------------------------------------------&gt; *)<br>        conn_set_state(c, conn_mwrite);<br>        c-&gt;msgcurr = 0;<br>    }<br>}</pre><p>The only relevant steps here are 1) item_get and 2) item_update. Steps marked as *) are mostly command parsing and I/O which will be discussed in later posts when we examine <strong>event driven</strong> mechanism.</p><h4>do_item_get</h4><p>Like other methods discussed before, item_get is a thread-safe wrapper of do_item_get.</p><pre>item *do_item_get(const char *key, const size_t nkey, const uint32_t hv, conn *c) {<br>    item *it = assoc_find(key, nkey, hv); // scr: ------------&gt; 1)<br>    if (it != NULL) {<br>        refcount_incr(&amp;it-&gt;refcount); // scr: ----------------&gt; 2)<br>...// scr: comments<br>    }<br>    int was_found = 0;<br><br>...// scr: verbose<br><br>    if (it != NULL) {<br>        was_found = 1;<br>        if (item_is_flushed(it)) {<br>...// scr: item flush<br>// scr: ------------------------------------------------------&gt; 3)<br>        } else if (it-&gt;exptime != 0 &amp;&amp; it-&gt;exptime &lt;= current_time) {<br>            do_item_unlink(it, hv);<br>            do_item_remove(it);<br>            it = NULL;<br>...// scr: stat &amp; verbose<br>            was_found = 3;<br>        } else { // scr: -------------------------------------&gt; 4)<br>            it-&gt;it_flags |= ITEM_FETCHED|ITEM_ACTIVE;<br>            DEBUG_REFCNT(it, &#39;+&#39;);<br>        }<br>    }<br><br>...// scr: verbose<br><br>    return it;<br>}</pre><p>1) Use the discussed assoc_find to locate the <strong>item</strong> using the <em>hash key</em>.</p><p>2) Increase the discussed <a href="http://holmeshe.me/understanding-memcached-source-code-IV/#do-item-link">reference count</a>.</p><p>3) If the <strong>item</strong> has expired, remove it. Note that do_item_unlink decreases the reference count held by the last step, and do_item_remove actually removes the <strong>item</strong>. These two methods will be discussed soon in <a href="http://holmeshe.me/understanding-memcached-source-code-VI/#Delete">item delete</a>.</p><p>4) Simply mark the <strong>item</strong> as ITEM_ACTIVE rather than perform <strong>item</strong> <em>bumping</em> which is offloaded to other operations associated procedures. This is part of the heuristic discussed in the beginning.</p><h4>do_item_update</h4><p>item_update is a thread-safe wrapper of do_item_update.</p><pre>void do_item_update(item *it) {<br>    MEMCACHED_ITEM_UPDATE(ITEM_key(it), it-&gt;nkey, it-&gt;nbytes);<br>    if (it-&gt;time &lt; current_time - ITEM_UPDATE_INTERVAL) {<br>        assert((it-&gt;it_flags &amp; ITEM_SLABBED) == 0);<br><br>        if ((it-&gt;it_flags &amp; ITEM_LINKED) != 0) {<br>            it-&gt;time = current_time; // scr: -----------------&gt; 1)<br>            if (!settings.lru_maintainer_thread) {<br>                item_unlink_q(it);<br>                item_link_q(it);<br>            }<br>        }<br>    }<br>}</pre><p>1) The only line effective in this method is to set the access time for the <strong>item</strong> in (passively) an interval of 60 seconds. lru_maintainer_thread is set to true by command line argument modern so the operations inside if (!settings.lru_maintainer_thread) is not applicable.</p><p>Next,</p><pre>&gt; delete test</pre><h3>Delete</h3><p>Call stack in normal execution,</p><pre>ref<br>1 |~Drive machine &amp; command parser<br>    |-process_delete_command<br>++    |-do_item_get<br>      |-do_item_unlink<br>        |-assoc_delete    (LRU II)<br>        |-item_unlink_q   (LRU I)<br>--      |-do_item_remove<br>--    |-do_item_remove<br>        |-do_item_free<br>          |-do_slabs_free (Slab II)</pre><h4>process_delete_command</h4><pre>static void process_delete_command(conn *c, token_t *tokens, const size_t ntokens) {<br>    char *key;<br>    size_t nkey;<br>    item *it;<br><br>...// scr: sanity check<br><br>    key = tokens[KEY_TOKEN].value;<br>    nkey = tokens[KEY_TOKEN].length;<br><br>...// scr: sanity check &amp; stat<br><br>    it = item_get(key, nkey, c); // scr: --------------------&gt; 1)<br>    if (it) {<br>        MEMCACHED_COMMAND_DELETE(c-&gt;sfd, ITEM_key(it), it-&gt;nkey);<br><br>...// scr: stat<br><br>        item_unlink(it); // scr: ----------------------------&gt; 2)<br>        item_remove(it);      /* release our reference */<br>        out_string(c, &quot;DELETED&quot;);<br>    } else {<br>...// scr: stat<br><br>        out_string(c, &quot;NOT_FOUND&quot;);<br>    }<br>}</pre><p>1) Get the <strong>item</strong> using item_get discussed in last section. Note that the reference count is increased in item_get.</p><p>2) Delete it.</p><h4>do_item_unlink</h4><p>item_unlink is a thread safe wrapper of do_item_unlink.</p><pre>void do_item_unlink(item *it, const uint32_t hv) {<br>...<br>    if ((it-&gt;it_flags &amp; ITEM_LINKED) != 0) {<br>        it-&gt;it_flags &amp;= ~ITEM_LINKED;<br>...// scr: stat<br>        assoc_delete(ITEM_key(it), it-&gt;nkey, hv); // scr: ---&gt; 1)<br>        item_unlink_q(it); // scr: --------------------------&gt; 2)<br>        do_item_remove(it); // scr: -------------------------&gt; 3)<br>    }<br>}</pre><p>1) As discussed in last post, <a href="http://holmeshe.me/understanding-memcached-source-code-IV/#assoc-delete-remove-from-hash-map">assoc_delete</a> removes the <strong>item</strong> from the <em>hash map</em>; and</p><p>2) <a href="http://holmeshe.me/understanding-memcached-source-code-IV/#item-unlink-q-remove-from-linked-list">item_unlink_q</a> removes the <strong>item</strong> from the <strong>LRU list</strong> that the <strong>item</strong> belongs to.</p><p>3) This time do_item_remove simply decreases the reference count. The <strong>item</strong> will be removed when do_item_remove is called the second time from</p><h4>do_item_remove</h4><p>item_remove is a thread safe wrapper of do_item_remove.</p><pre>void do_item_remove(item *it) {<br>...// scr: sanity check<br><br>    if (refcount_decr(&amp;it-&gt;refcount) == 0) { // scr: --------&gt; 1)<br>        item_free(it);<br>    }<br>}<br>...<br>void item_free(item *it) {<br>    size_t ntotal = ITEM_ntotal(it);<br>    unsigned int clsid;<br>...// scr: sanity check<br><br>    /* so slab size changer can tell later if item is already free or not */<br>    clsid = ITEM_clsid(it); // scr: -------------------------&gt; 2)<br>    DEBUG_REFCNT(it, &#39;F&#39;);<br>    slabs_free(it, ntotal, clsid); // scr: ------------------&gt; 3)<br>}</pre><p>1) Decrease the reference count, if it reaches 0, goto 2) and free the <strong>item</strong>.</p><p>2) Use ITEM_clsid to get the <em>slab class</em> the <strong>item</strong> belongs. This macro removes the <em>list type</em> from slabs_clsid.</p><p>3) Call <a href="http://holmeshe.me/understanding-memcached-source-code-II/#do-slabs-free">slabs_free</a> to release the memory to slab subsystem.</p><h3>Create</h3><p>The <strong>Item</strong> creating procedure is divided into several logic fragments by the mentioned <strong>drive machine</strong>, 1) creating an empty <strong>item</strong> object with the <em>key</em> and other <em>meta data</em> sent through; 2) read the value (from the <em>socket</em>) and fill the <strong>item</strong> object with it; and 3) <em>link</em> the <strong>item object</strong>. The workflow controller — <strong>drive machine</strong> will be discussed in the next post.</p><p>Now we send an add command to the <strong>Memcached</strong> instance.</p><pre>&gt; add test 0 60 11 (\r\n)<br>&gt; hello world</pre><h3>Creating an empty item object</h3><p>After the first line of the above command</p><pre>&gt; add test 0 60 11 (\r\n)</pre><p>the procedure described in this section starts, the call stack of which is,</p><pre>ref<br>1 |~Drive machine &amp; command parser<br>    |-process_update_command<br>      |-do_item_alloc<br>        |-slabs_clsid                (Slab III)<br>++      |-do_slabs_alloc             (Slab III)<br>        |-lru_pull_tail (on hot list)<br>          |-do_item_update_nolock    (same to do_item_update)<br>          |-do_item_remove<br>          |-item_link_q              (LRU I)<br>          |-do_item_remove<br>        |-lru_pull_tail (on warm list)<br>          |-same as hot list<br>        |-lru_pull_tail (on cold list)<br>          |-do_item_unlink_nolock    (same to do_item_unlink LRU I)</pre><p>We start from</p><h4>process_update_command</h4><pre>static void process_update_command(conn *c, token_t *tokens, const size_t ntokens, int comm, bool handle_cas) {<br>    char *key;<br>    size_t nkey;<br>    unsigned int flags;<br>    int32_t exptime_int = 0;<br>    time_t exptime;<br>    int vlen;<br>    uint64_t req_cas_id=0;<br>    item *it;<br><br>...// scr: irrelevant code &amp; sanity checks<br><br>    key = tokens[KEY_TOKEN].value; // scr: -----------------&gt; 1)<br>    nkey = tokens[KEY_TOKEN].length;<br><br>    if (! (safe_strtoul(tokens[2].value, (uint32_t *)&amp;flags)<br>           &amp;&amp; safe_strtol(tokens[3].value, &amp;exptime_int)<br>           &amp;&amp; safe_strtol(tokens[4].value, (int32_t *)&amp;vlen))) {<br>        out_string(c, &quot;CLIENT_ERROR bad command line format&quot;);<br>        return;<br>    }<br><br>    /* Ubuntu 8.04 breaks when I pass exptime to safe_strtol */<br>    exptime = exptime_int;<br><br>...// scr: cas &amp; sanity checks<br><br>    vlen += 2; // scr: -------------------------------------&gt; 2)<br><br>...// scr: stat<br><br>    it = item_alloc(key, nkey, flags, realtime(exptime), vlen);//3)<br><br>...// scr: cas &amp; error handling<br><br>    c-&gt;item = it; // scr: ----------------------------------&gt; 4)<br>    c-&gt;ritem = ITEM_data(it);<br>    c-&gt;rlbytes = it-&gt;nbytes;<br>    c-&gt;cmd = comm;<br>    conn_set_state(c, conn_nread);<br>}</pre><p>1) Set the <em>key</em> (i.e., test), as well as the <em>meta data</em> (i.e., flags, 0; exptime, 60; vlen, 11), to local variables.</p><p>2) Increase vlen by 2, to populate the \n\r in addition to the <em>key</em> string.</p><p>3) Call item_alloc to allocate the memory (from <a href="http://holmeshe.me/understanding-memcached-source-code-III/">slab</a>) for the <strong>item</strong>.</p><p>4) After item_alloc is called, set the properties of conn. Here ritem points to the data portion of an <a href="http://holmeshe.me/understanding-memcached-source-code-IV/#Memory-layout-of-an-item-chunk">item chunk</a>; and rlbytes is set to vlen. These two fields will be used to populate the data portion with the content, i.e., hello world, in the next post.</p><h4>do_item_alloc</h4><p>Unlike other methods we have discussed, item_alloc is a wrapper of do_item_alloc without adding any locks. I would assume this wrapper is added simply for consistent code style.</p><pre>item *do_item_alloc(char *key, const size_t nkey, const unsigned int flags,<br>                    const rel_time_t exptime, const int nbytes,<br>                    const uint32_t cur_hv) {<br>    int i;<br>    uint8_t nsuffix;<br>    item *it = NULL;<br>    char suffix[40];<br>    unsigned int total_chunks;       // scr: -----------------&gt; 1)<br>    size_t ntotal = item_make_header(nkey + 1, flags, nbytes, suffix, &amp;nsuffix);<br>... // scr: cas<br><br>    unsigned int id = slabs_clsid(ntotal); // scr:------------&gt; 2)<br>    if (id == 0)<br>        return 0;<br><br>    /* If no memory is available, attempt a direct LRU juggle/eviction */<br>    /* This is a race in order to simplify lru_pull_tail; in cases where<br>     * locked items are on the tail, you want them to fall out and cause<br>     * occasional OOM&#39;s, rather than internally work around them.<br>     * This also gives one fewer code path for slab alloc/free<br>     */<br>    for (i = 0; i &lt; 5; i++) {<br>        /* Try to reclaim memory first */<br>... // scr: legacy, no lru_maintainer_thread<br>        it = slabs_alloc(ntotal, id, &amp;total_chunks, 0); // scr:3)<br>... // scr: no-expire setting<br>        if (it == NULL) {<br>            if (settings.lru_maintainer_thread) { // scr: ---&gt; 4)<br>                lru_pull_tail(id, HOT_LRU, total_chunks, false, cur_hv);<br>                lru_pull_tail(id, WARM_LRU, total_chunks, false, cur_hv);<br>                lru_pull_tail(id, COLD_LRU, total_chunks, true, cur_hv);<br>            } else {<br>... // scr: legacy, no lru_maintainer_thread<br>            }<br>        } else {<br>            break;<br>        <br>    }<br><br>... // scr: stat &amp; sanity check<br><br>    /* Refcount is seeded to 1 by slabs_alloc() */<br>    it-&gt;next = it-&gt;prev = it-&gt;h_next = 0; // scr: -----------&gt; 5)<br>    /* Items are initially loaded into the HOT_LRU. This is &#39;0&#39; but I want at<br>     * least a note here. Compiler (hopefully?) optimizes this out.<br>     */<br>    if (settings.lru_maintainer_thread) {<br>... // scr: no expire setting<br>        } else {<br>            id |= HOT_LRU; // scr: --------------------------&gt; 6)<br>        }<br>    } else {<br>... // scr: legacy, no lru_maintainer_thread<br>    }<br>    it-&gt;slabs_clsid = id; // scr: ---------------------------&gt; 7)<br><br>    DEBUG_REFCNT(it, &#39;*&#39;);<br>    it-&gt;it_flags = settings.use_cas ? ITEM_CAS : 0;<br>    it-&gt;nkey = nkey;<br>    it-&gt;nbytes = nbytes;<br>    memcpy(ITEM_key(it), key, nkey);<br>    it-&gt;exptime = exptime;<br>    memcpy(ITEM_suffix(it), suffix, (size_t)nsuffix);<br>    it-&gt;nsuffix = nsuffix;<br>    return it;<br>}</pre><p>1) item_make_header initializes <a href="http://holmeshe.me/understanding-memcached-source-code-IV/#Core-data-structure-item">suffix</a> portion of the <a href="http://holmeshe.me/understanding-memcached-source-code-IV/#Memory-layout-of-an-item-chunk">item chunk</a> using the <em>meta data</em> (flags) and <em>key</em>.</p><p>2), 3) are discussed in detail in <a href="http://holmeshe.me/understanding-memcached-source-code-III/">Slab III</a>. To recap, <a href="http://holmeshe.me/understanding-memcached-source-code-III/#slabs-clsid">slabs_clsid</a> select the most optimal <em>slab class</em> and <a href="http://holmeshe.me/understanding-memcached-source-code-III/#do-slabs-alloc">slab_alloc</a> allocates one <strong>item chunk</strong> from <strong>slab</strong> sub-system.</p><p>4) If slab_alloc fails, try to release some memory using lru_pull_tail and retry the allocation for at most 5 times. lru_pull_tail is the focus of the <a href="http://holmeshe.me/understanding-memcached-source-code-VI/#lru-pull-tail">next section</a>.</p><p>5) Initialize the <a href="http://holmeshe.me/understanding-memcached-source-code-IV/#Core-data-structure-item">pointers</a> of <strong>LRU list</strong> and <em>hash collision list</em>.</p><p>6) Set the <em>list type</em> (HOT_LRU) to the <a href="http://holmeshe.me/understanding-memcached-source-code-IV/#Core-data-structure-item">slabs_clsid</a>, which indicates that this <strong>item</strong> belongs to the “HOT” <strong>LRU list</strong> of its respective <em>slab class</em>.</p><p>7) Initialize <a href="http://holmeshe.me/understanding-memcached-source-code-IV/#Core-data-structure-item">other fields</a> of <strong>item</strong>.</p><h4>lru_pull_tail</h4><pre>static int lru_pull_tail(const int orig_id, const int cur_lru,<br>        const unsigned int total_chunks, const bool do_evict, const uint32_t cur_hv) {<br>    item *it = NULL;<br>    int id = orig_id; // scr: -------------------------------&gt; p)<br>    int removed = 0;<br>    if (id == 0)<br>        return 0;<br><br>    int tries = 5;<br>    item *search;<br>    item *next_it;<br>    void *hold_lock = NULL;<br>    unsigned int move_to_lru = 0;<br>    uint64_t limit;<br><br>    id |= cur_lru; // scr: ----------------------------------&gt; p)<br>    pthread_mutex_lock(&amp;lru_locks[id]);<br>    search = tails[id]; // scr: -----------------------------&gt; p)<br>    /* We walk up *only* for locked items, and if bottom is expired. */<br>    for (; tries &gt; 0 &amp;&amp; search != NULL; tries--, search=next_it) {//s: p)<br>        /* we might relink search mid-loop, so search-&gt;prev isn&#39;t reliable */<br>        next_it = search-&gt;prev; // scr: ---------------------&gt; p)<br>...// scr: irrelevant code here<br>        uint32_t hv = hash(ITEM_key(search), search-&gt;nkey);<br>        /* Attempt to hash item lock the &quot;search&quot; item. If locked, no<br>         * other callers can incr the refcount. Also skip ourselves. */<br>        if (hv == cur_hv || (hold_lock = item_trylock(hv)) == NULL)<br>            continue;<br>        /* Now see if the item is refcount locked */<br>        if (refcount_incr(&amp;search-&gt;refcount) != 2) { // scr: &gt; s)<br>            /* Note pathological case with ref&#39;ed items in tail.<br>             * Can still unlink the item, but it won&#39;t be reusable yet */<br>            itemstats[id].lrutail_reflocked++;<br>            /* In case of refcount leaks, enable for quick workaround. */<br>            /* WARNING: This can cause terrible corruption */<br>            if (settings.tail_repair_time &amp;&amp;<br>                    search-&gt;time + settings.tail_repair_time &lt; current_time) {<br>                itemstats[id].tailrepairs++;<br>                search-&gt;refcount = 1;<br>                /* This will call item_remove -&gt; item_free since refcnt is 1 */<br>                do_item_unlink_nolock(search, hv);<br>                item_trylock_unlock(hold_lock);<br>                continue;<br>            }<br>        }<br><br>        /* Expired or flushed */ // scr: -------------------&gt; e1)<br>        if ((search-&gt;exptime != 0 &amp;&amp; search-&gt;exptime &lt; current_time)<br>            || item_is_flushed(search)) {<br>...// scr: stat<br>            /* refcnt 2 -&gt; 1 */<br>            do_item_unlink_nolock(search, hv);<br>            /* refcnt 1 -&gt; 0 -&gt; item_free */<br>            do_item_remove(search);<br>            item_trylock_unlock(hold_lock);<br>            removed++;<br><br>            /* If all we&#39;re finding are expired, can keep going */<br>            continue;<br>        }<br><br>        /* If we&#39;re HOT_LRU or WARM_LRU and over size limit, send to COLD_LRU.<br>         * If we&#39;re COLD_LRU, send to WARM_LRU unless we need to evict<br>         */<br>        switch (cur_lru) {<br>            case HOT_LRU: // scr: ---------------------------&gt; 1)<br>                limit = total_chunks * settings.hot_lru_pct / 100;<br>            case WARM_LRU:<br>                limit = total_chunks * settings.warm_lru_pct / 100; // 1)<br>                if (sizes[id] &gt; limit) { // scr: ------------&gt; 2)<br>...// scr: stat<br>                    move_to_lru = COLD_LRU;<br>                    do_item_unlink_q(search);<br>                    it = search;<br>                    removed++;<br>                    break;<br>                } else if ((search-&gt;it_flags &amp; ITEM_ACTIVE) != 0) { //e3)<br>...// scr: stat<br>                    search-&gt;it_flags &amp;= ~ITEM_ACTIVE;<br>                    do_item_update_nolock(search);<br>                    do_item_remove(search);<br>                    item_trylock_unlock(hold_lock);<br>                } else { // scr: ----------------------------&gt; 3)<br>                    /* Don&#39;t want to move to COLD, not active, bail out */<br>                    it = search;<br>                }<br>                break;<br>            case COLD_LRU:<br>                it = search; /* No matter what, we&#39;re stopping */<br>                if (do_evict) {<br>                    if (settings.evict_to_free == 0) {<br>...// scr: not applied here<br>                    }<br>...// scr: stat<br>                    LOGGER_LOG(NULL, LOG_EVICTIONS, LOGGER_EVICTION, search);<br>                    do_item_unlink_nolock(search, hv); // scr: 4)<br>                    removed++;<br>                    if (settings.slab_automove == 2) {<br>...// scr: not applied here<br>                    }<br>                } else if<br>...// scr: not applied here<br>                }<br>                break;<br>        }<br>        if (it != NULL)<br>            break;<br>    }<br><br>    pthread_mutex_unlock(&amp;lru_locks[id]);<br><br>    if (it != NULL) { // scr: ------------------------------&gt; e2)<br>        if (move_to_lru) {<br>            it-&gt;slabs_clsid = ITEM_clsid(it);<br>            it-&gt;slabs_clsid |= move_to_lru;<br>            item_link_q(it);<br>        }<br>        do_item_remove(it);<br>        item_trylock_unlock(hold_lock);<br>    }<br><br>    return removed;<br>}</pre><p><strong>Method start &amp; end</strong></p><p>p) This method starts by selecting the tail element of the designated <strong>LRU list</strong> using the <strong>slab class</strong><em> </em>id and the <em>list type,</em> assuming that the element can be a release candidate. And it iterates over (at most 5 entries) the list in reverse order to find a entry in case that elements near the tail are recently accessed.</p><p>s) For each <strong>item</strong> selected, increase its <em>reference count</em>. In normal situation, the original value of <em>reference count</em> should be 1 (as you will see in the <a href="http://localhost:4000/understanding-memcached-source-code-VI/#Populate-the-data-amp-Link-the-item">last step</a> of the create operation). Hence a != 2 value after the increment indicates an exception which needs to be corrected. Note that the <em>reference count</em> is now 2 so it is required to decrease at least one time (back to 1) when the processing of the current <strong>item</strong> is done (e1, e2 or e3 is reached).</p><p>e1) Remove the <strong>item</strong> directly when an expiration is detected. Here the do_item_unlink_nolock is exactly the same as the discussed <a href="http://holmeshe.me/understanding-memcached-source-code-VI/#item-unlink">do_item_unlink</a> (I think the code is duplicated to emphasize that this method is not thread-safe), and it follows the same “unlink and remove” routine as in <a href="http://holmeshe.me/understanding-memcached-source-code-VI/#Delete">item delete</a>.</p><p>e2) When a candidate is found, we might need to relocate it to another <strong>list</strong> (when move_to_lru is set in the switch case) by calling <a href="http://holmeshe.me/understanding-memcached-source-code-IV/#item-link-q-add-to-linked-list">item_link_q</a>. And we do need to call <a href="http://holmeshe.me/understanding-memcached-source-code-VI/##item-remove">do_item_remove</a> to reduce the reference count back to 1. The decision is made by the steps discussed bellow.</p><p>e3) If an <strong>item</strong> is recently accessed, reset the ITEM_ACTIVE flag; <em>bump</em> it to the head of the list; decrease its <em>reference count</em> and iterate to the next one (maximum 5 times). Remember that the flag ITEM_ACTIVE is set by <a href="http://holmeshe.me/understanding-memcached-source-code-VI/#item-get">item_get</a>, and here is the place where the <strong>item</strong> gets <em>bumped</em>.</p><p><strong>Hot &amp; warm</strong></p><p>1) The only difference of HOT_LRU and WARM_LRU is the threshold (limit) which are indicated by their respective configurations hot_lru_pct and warm_lru_pct.</p><p>2) If the threshold of HOT_LRU or WARM_LRU is reached, remove the <strong>item</strong> from the current list using <a href="http://holmeshe.me/understanding-memcached-source-code-IV/#item-unlink-q-remove-from-linked-list">do_item_unlink_q</a>, and goto e2). Therefore, e2) is responsible to relink it to the COLD_LRU and decrease the reference count.</p><p>3) If the current <strong>item</strong> is not “active”, and the threshold is not reached, finish this method without any <strong>item</strong> relocation, nor release.</p><p><strong>Cold</strong></p><p>4) If there are any <strong>item</strong> in the list, evict it directly with the discussed do_item_unlink_nolock to free up its resource, and goto e2). Note that the default values of evict_to_free and slab_automove are set to values that disable their respective if blocks.</p><p>Now we input the second line of the command</p><pre>&gt; hello world</pre><p>and trigger the following procedures.</p><h3>Populate the item with content</h3><p>As mentioned in <a href="http://holmeshe.me/understanding-memcached-source-code-VI/#process-update-command">process_update_command</a>, the content we input is populated to conn.item using conn.ritem and conn.rlbytes. This step is handled by <strong>drive machine</strong> which will be discussed in detail in the next post.</p><p>Now we consider conn.item is filled with all relevant information, hence the next and final step is to</p><h3>Link the item</h3><p>the call stack of this step is</p><pre>ref<br>2 |~Drive machine &amp; command parser<br>    |-complete_nread<br>      |-complete_nread_ascii<br>        |-do_store_item<br>        |=do_item_link      (LRU I)<br>--      |-do_item_remove</pre><p>complete_nread checks the protocol in use and moves directly to</p><h4>complete_nread_ascii</h4><pre>static void complete_nread_ascii(conn *c) {<br>    assert(c != NULL);<br><br>    item *it = c-&gt;item;<br>    int comm = c-&gt;cmd;<br>    enum store_item_type ret;<br>...// scr: stat<br><br>    if (strncmp(ITEM_data(it) + it-&gt;nbytes - 2, &quot;\r\n&quot;, 2) != 0) {<br>        out_string(c, &quot;CLIENT_ERROR bad data chunk&quot;); // scr: &gt; 1)<br>    } else {<br>      ret = store_item(it, comm, c);<br><br>      switch (ret) {<br>      case STORED:<br>          out_string(c, &quot;STORED&quot;);<br>          break;<br>      case EXISTS:<br>          out_string(c, &quot;EXISTS&quot;);<br>          break;<br>      case NOT_FOUND:<br>          out_string(c, &quot;NOT_FOUND&quot;);<br>          break;<br>      case NOT_STORED:<br>          out_string(c, &quot;NOT_STORED&quot;);<br>          break;<br>      default:<br>          out_string(c, &quot;SERVER_ERROR Unhandled storage type.&quot;);<br>      }<br><br>    }<br>    // scr: --------------------------------------------------&gt; 2)<br>    item_remove(c-&gt;item);       /* release the c-&gt;item reference */<br>    c-&gt;item = 0;<br>}</pre><p>1) Call store_item to link the <strong>item</strong> to the <strong>LRU list</strong> and <strong>hash map</strong>.</p><p>2) The <em>reference count</em> is set to 1 by <a href="http://holmeshe.me/understanding-memcached-source-code-III/#do-slabs-alloc">do_slab_alloc</a> in <a href="http://holmeshe.me/understanding-memcached-source-code-VI/#do-item-alloc">do_item_alloc</a> and increased by <a href="http://holmeshe.me/understanding-memcached-source-code-IV/#do-item-link">do_item_link</a> in <a href="http://holmeshe.me/understanding-memcached-source-code-VI/#do-store-item">do_store_item</a>. So reduce it to the normal value, 1, with <a href="http://holmeshe.me/understanding-memcached-source-code-VI/#do-item-remove">item_remove</a>. The methods of those have all been discussed in detail.</p><h4>do_store_item</h4><pre>enum store_item_type do_store_item(item *it, int comm, conn *c, const uint32_t hv) {<br>    char *key = ITEM_key(it);<br>    item *old_it = do_item_get(key, it-&gt;nkey, hv, c); // scr: &gt; 1)<br>    enum store_item_type stored = NOT_STORED;<br><br>    item *new_it = NULL;<br>    uint32_t flags;<br><br>    if (old_it != NULL &amp;&amp; comm == NREAD_ADD) {<br>... // scr: update logic<br>    } else if (!old_it &amp;&amp; (comm == NREAD_REPLACE<br>        || comm == NREAD_APPEND || comm == NREAD_PREPEND))<br>    {<br>        /* replace only replaces an existing value; don&#39;t store */<br>    } else if (comm == NREAD_CAS) {<br>... // scr: cas<br>    } else {<br>...<br>        if (comm == NREAD_APPEND || comm == NREAD_PREPEND) {<br>... // scr: comm is NREAD_ADD (1)<br>        }<br><br>        if (stored == NOT_STORED &amp;&amp; failed_alloc == 0) {<br>            if (old_it != NULL)<br>                item_replace(old_it, it, hv);<br>            else<br>                do_item_link(it, hv); // scr: ----------------&gt; 2)<br><br>...<br><br>            stored = STORED;<br>        }<br>    }<br><br>... // scr: irrelevant code<br><br>// scr: cas<br>    LOGGER_LOG(c-&gt;thread-&gt;l, LOG_MUTATIONS, LOGGER_ITEM_STORE, NULL,<br>            stored, comm, ITEM_key(it), it-&gt;nkey);<br><br>    return stored;<br>}</pre><p>1) The newly created <strong>item</strong> exists only in the <strong>slab</strong> subsystem, hence do_item_get returns null as there is no such record in <strong>hash map</strong> yet.</p><p>2) So in the context of <em>item creation</em>, do_store_item is essentially the same as do_item_link.</p><h3>Reference</h3><p><a href="https://memcached.org/blog/modern-lru/">Replacing the cache replacement algorithm in memcached</a></p><p><a href="http://hourlyapps.blogspot.com/2010/06/examples-of-memcached-commands.html">Examples of Memcached telnet commands</a></p><p><a href="https://blog.elijaa.org/2010/05/21/memcached-telnet-command-summary/#delete">Memcached telnet command summary</a></p><p><em>Originally published at </em><a href="http://holmeshe.me/understanding-memcached-source-code-VI/"><em>holmeshe.me</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=87d1c7497cb9" width="1" height="1" alt=""><hr><p><a href="https://medium.com/source-code/understanding-the-memcached-source-code-lru-iii-87d1c7497cb9">Understanding The Memcached Source Code — LRU III</a> was originally published in <a href="https://medium.com/source-code">source code</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>