{"action":"created","comment":{"url":"https://api.github.com/repos/tempesta-tech/tempesta/pulls/comments/67379880","id":67379880,"diff_hunk":"@@ -92,72 +93,93 @@ ss_skb_alloc_pages(size_t len)\n }\n \n static inline int\n-ss_skb_frag_len(skb_frag_t *frag)\n+ss_skb_frag_len(const skb_frag_t *frag)\n {\n \treturn frag->page_offset + frag->size;\n }\n \n /**\n- * Scan paged fragments array for fragments placed in the same page\n- * with @frag and check if the page has enough room to add @len bytes.\n- * The fragments are scanned until @refcnt reaches zero. Otherwise,\n- * the page is in use outside of the SKB, so give up on checking it.\n- * @return pointer to the last fragment in the page.\n+ * Find a page that has room for @len bytes.\n+ * Return true if the room is found, or false otherwise.\n+ * If the room is found, fill @f_out that describes the location of the room.\n+ *\n+ * The assumption is that there can be sufficient room available at the\n+ * start or at the end of a page that holds this SKB's paged fragments.\n+ *\n+ * For a group of paged fragments located in the same page the available\n+ * headroom and tailroom are calculated. If @len is less than both of\n+ * those, then the next group of fragments and the page they're located in\n+ * are considered. That is repeated until all paged fragments and the\n+ * respective pages are checked. Of pages that do have sufficient room\n+ * available, only those pages that don't have users outside of this SKB\n+ * are suitable.\n+ *\n+ * Several notes regarding the algorithm and the underlinings:\n+ * - If a page is still used for allocation of fragments by one of the\n+ *   kernel's allocators, then that page is owned by the allocator. That\n+ *   page's reference count will not get down to 1 until the page is released\n+ *   by the allocator.\n+ * - Tempesta's allocator has no notion of \"owning\" a page that is used\n+ *   for allocation of fragments. These fragments are used for the SKB\n+ *   structure itself, as well as for skb->head. The page used for these\n+ *   parts of an SKB may propagate to a paged fragment when a part of the\n+ *   linear data is mapped to a fragment. The algorithm skips those pages to\n+ *   avoid an unwanted memory corruption.\n+ * - map[] array is used to speed up the search. Once fragments that belong\n+ *   in the same page are checked, there's no need to check them again in the\n+ *   next iteration.\n  */\n-static skb_frag_t *\n-__check_frag_room(struct sk_buff *skb, skb_frag_t *frag, int len)\n+static bool\n+__lookup_pgfrag_room(const struct sk_buff *skb, int len, skb_frag_t *f_out)\n {\n-\tint i, sz, sz2, refcnt;\n-\tstruct page *pg = skb_frag_page(frag);\n-\tskb_frag_t *frag2, *ret = frag;\n+\tint i, k, owners;\n+\tchar map[MAX_SKB_FRAGS];\n+\tconst skb_frag_t *f_base, *f_this;\n+\tunsigned int p_size, h_room, t_room;\n+\tstruct page *p_base, *p_skb_head = virt_to_head_page(skb->head);\n \n-\tif ((refcnt = page_count(pg)) == 1)\n-\t\treturn frag; /* no other users */\n+\tmemset(map, 0, sizeof(map));\n \n-\tsz = PAGE_SIZE - ss_skb_frag_len(frag);\n-\tfor (i = skb_shinfo(skb)->nr_frags - 1; i >= 0 ; --i) {\n-\t\tfrag2 = &skb_shinfo(skb)->frags[i];\n-\t\tif (frag2 == frag || pg != skb_frag_page(frag2))\n+\tfor (i = 0; i < skb_shinfo(skb)->nr_frags; i++) {\n+\t\tif (map[i])\n \t\t\tcontinue;\n-\t\tsz2 = PAGE_SIZE - ss_skb_frag_len(frag2);\n-\t\tif (sz2 < len)\n-\t\t\treturn NULL;\n-\t\tif (sz2 < sz) {\n-\t\t\tsz = sz2;\n-\t\t\tret = frag2;\n-\t\t}\n-\t\t/* Return localy referenced pages only. */\n-\t\tif (--refcnt == 1)\n-\t\t\treturn ret;\n-\t}\n \n-\t/* The page is used outside of this SKB. */\n-\treturn NULL;\n-}\n+\t\tf_base = &skb_shinfo(skb)->frags[i];\n+\t\tp_base = compound_head(skb_frag_page(f_base));\n+\t\tif (p_base == p_skb_head)\n+\t\t\tcontinue;\n \n-/**\n- * Look up a page fragment that has room for @len bytes.\n- */\n-static skb_frag_t *\n-__lookup_pgfrag_room(struct sk_buff *skb, int len)\n-{\n-\tint i;\n+\t\towners = page_count(p_base);\n+\t\tp_size = h_room = t_room = PAGE_SIZE << compound_order(p_base);\n \n-\t/*\n-\t * Iterate in reverse order to use likely moving fragments.\n-\t * Thus we find free room more frequently and skb fragments\n-\t * utilize memory limits better.\n-\t */\n-\tfor (i = skb_shinfo(skb)->nr_frags - 1; i >= 0; --i) {\n-\t\tskb_frag_t *frag = &skb_shinfo(skb)->frags[i];\n-\t\tif ((int)PAGE_SIZE - ss_skb_frag_len(frag) < len)\n-\t\t\tcontinue;\n-\t\tfrag = __check_frag_room(skb, frag, len);\n-\t\tif (frag)\n-\t\t\treturn frag;\n+\t\tfor (k = i; k < skb_shinfo(skb)->nr_frags; k++) {\n+\t\t\tif (map[k])\n+\t\t\t\tcontinue;\n+\n+\t\t\tf_this = &skb_shinfo(skb)->frags[k];\n+\t\t\tif (compound_head(skb_frag_page(f_this)) != p_base)\n+\t\t\t\tcontinue;\n+\n+\t\t\tif ((map[k] = 1, map[i]) > 1)\n+\t\t\t\tcontinue;\n+\n+\t\t\th_room = min(h_room, f_this->page_offset);\n+\t\t\tt_room = min(t_room, p_size - ss_skb_frag_len(f_this));\n+\t\t\tmap[i] = map[i] + !!(len > h_room && len > t_room);","path":"tempesta_fw/ss_skb.c","position":134,"original_position":134,"commit_id":"4ec7d53ee8af0a33c830f914b6da6e7b8617b83f","original_commit_id":"7ae8d515a9d9cae982ac7baea317654ccf810ac5","user":{"login":"krizhanovsky","id":884694,"avatar_url":"https://avatars.githubusercontent.com/u/884694?v=3","gravatar_id":"","url":"https://api.github.com/users/krizhanovsky","html_url":"https://github.com/krizhanovsky","followers_url":"https://api.github.com/users/krizhanovsky/followers","following_url":"https://api.github.com/users/krizhanovsky/following{/other_user}","gists_url":"https://api.github.com/users/krizhanovsky/gists{/gist_id}","starred_url":"https://api.github.com/users/krizhanovsky/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/krizhanovsky/subscriptions","organizations_url":"https://api.github.com/users/krizhanovsky/orgs","repos_url":"https://api.github.com/users/krizhanovsky/repos","events_url":"https://api.github.com/users/krizhanovsky/events{/privacy}","received_events_url":"https://api.github.com/users/krizhanovsky/received_events","type":"User","site_admin":false},"body":"`map[i] += !!(len > h_room && len > t_room);`?","created_at":"2016-06-16T16:37:58Z","updated_at":"2016-06-16T16:37:58Z","html_url":"https://github.com/tempesta-tech/tempesta/pull/557#discussion_r67379880","pull_request_url":"https://api.github.com/repos/tempesta-tech/tempesta/pulls/557","_links":{"self":{"href":"https://api.github.com/repos/tempesta-tech/tempesta/pulls/comments/67379880"},"html":{"href":"https://github.com/tempesta-tech/tempesta/pull/557#discussion_r67379880"},"pull_request":{"href":"https://api.github.com/repos/tempesta-tech/tempesta/pulls/557"}}},"pull_request":{"url":"https://api.github.com/repos/tempesta-tech/tempesta/pulls/557","id":73472355,"html_url":"https://github.com/tempesta-tech/tempesta/pull/557","diff_url":"https://github.com/tempesta-tech/tempesta/pull/557.diff","patch_url":"https://github.com/tempesta-tech/tempesta/pull/557.patch","issue_url":"https://api.github.com/repos/tempesta-tech/tempesta/issues/557","number":557,"state":"open","locked":false,"title":"rework __lookup_pgfrag_room","user":{"login":"milabs","id":624823,"avatar_url":"https://avatars.githubusercontent.com/u/624823?v=3","gravatar_id":"","url":"https://api.github.com/users/milabs","html_url":"https://github.com/milabs","followers_url":"https://api.github.com/users/milabs/followers","following_url":"https://api.github.com/users/milabs/following{/other_user}","gists_url":"https://api.github.com/users/milabs/gists{/gist_id}","starred_url":"https://api.github.com/users/milabs/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/milabs/subscriptions","organizations_url":"https://api.github.com/users/milabs/orgs","repos_url":"https://api.github.com/users/milabs/repos","events_url":"https://api.github.com/users/milabs/events{/privacy}","received_events_url":"https://api.github.com/users/milabs/received_events","type":"User","site_admin":false},"body":"","created_at":"2016-06-11T16:38:47Z","updated_at":"2016-06-16T16:37:58Z","closed_at":null,"merged_at":null,"merge_commit_sha":"bd7c04009c3420e98c5892cb9cff59ebc9af9784","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/tempesta-tech/tempesta/pulls/557/commits","review_comments_url":"https://api.github.com/repos/tempesta-tech/tempesta/pulls/557/comments","review_comment_url":"https://api.github.com/repos/tempesta-tech/tempesta/pulls/comments{/number}","comments_url":"https://api.github.com/repos/tempesta-tech/tempesta/issues/557/comments","statuses_url":"https://api.github.com/repos/tempesta-tech/tempesta/statuses/4ec7d53ee8af0a33c830f914b6da6e7b8617b83f","head":{"label":"tempesta-tech:im-issue-447","ref":"im-issue-447","sha":"4ec7d53ee8af0a33c830f914b6da6e7b8617b83f","user":{"login":"tempesta-tech","id":10939672,"avatar_url":"https://avatars.githubusercontent.com/u/10939672?v=3","gravatar_id":"","url":"https://api.github.com/users/tempesta-tech","html_url":"https://github.com/tempesta-tech","followers_url":"https://api.github.com/users/tempesta-tech/followers","following_url":"https://api.github.com/users/tempesta-tech/following{/other_user}","gists_url":"https://api.github.com/users/tempesta-tech/gists{/gist_id}","starred_url":"https://api.github.com/users/tempesta-tech/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tempesta-tech/subscriptions","organizations_url":"https://api.github.com/users/tempesta-tech/orgs","repos_url":"https://api.github.com/users/tempesta-tech/repos","events_url":"https://api.github.com/users/tempesta-tech/events{/privacy}","received_events_url":"https://api.github.com/users/tempesta-tech/received_events","type":"Organization","site_admin":false},"repo":{"id":23121600,"name":"tempesta","full_name":"tempesta-tech/tempesta","owner":{"login":"tempesta-tech","id":10939672,"avatar_url":"https://avatars.githubusercontent.com/u/10939672?v=3","gravatar_id":"","url":"https://api.github.com/users/tempesta-tech","html_url":"https://github.com/tempesta-tech","followers_url":"https://api.github.com/users/tempesta-tech/followers","following_url":"https://api.github.com/users/tempesta-tech/following{/other_user}","gists_url":"https://api.github.com/users/tempesta-tech/gists{/gist_id}","starred_url":"https://api.github.com/users/tempesta-tech/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tempesta-tech/subscriptions","organizations_url":"https://api.github.com/users/tempesta-tech/orgs","repos_url":"https://api.github.com/users/tempesta-tech/repos","events_url":"https://api.github.com/users/tempesta-tech/events{/privacy}","received_events_url":"https://api.github.com/users/tempesta-tech/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/tempesta-tech/tempesta","description":"High performance HTTP accelerator and firewall for WAF and DDoS prevention","fork":false,"url":"https://api.github.com/repos/tempesta-tech/tempesta","forks_url":"https://api.github.com/repos/tempesta-tech/tempesta/forks","keys_url":"https://api.github.com/repos/tempesta-tech/tempesta/keys{/key_id}","collaborators_url":"https://api.github.com/repos/tempesta-tech/tempesta/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/tempesta-tech/tempesta/teams","hooks_url":"https://api.github.com/repos/tempesta-tech/tempesta/hooks","issue_events_url":"https://api.github.com/repos/tempesta-tech/tempesta/issues/events{/number}","events_url":"https://api.github.com/repos/tempesta-tech/tempesta/events","assignees_url":"https://api.github.com/repos/tempesta-tech/tempesta/assignees{/user}","branches_url":"https://api.github.com/repos/tempesta-tech/tempesta/branches{/branch}","tags_url":"https://api.github.com/repos/tempesta-tech/tempesta/tags","blobs_url":"https://api.github.com/repos/tempesta-tech/tempesta/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/tempesta-tech/tempesta/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/tempesta-tech/tempesta/git/refs{/sha}","trees_url":"https://api.github.com/repos/tempesta-tech/tempesta/git/trees{/sha}","statuses_url":"https://api.github.com/repos/tempesta-tech/tempesta/statuses/{sha}","languages_url":"https://api.github.com/repos/tempesta-tech/tempesta/languages","stargazers_url":"https://api.github.com/repos/tempesta-tech/tempesta/stargazers","contributors_url":"https://api.github.com/repos/tempesta-tech/tempesta/contributors","subscribers_url":"https://api.github.com/repos/tempesta-tech/tempesta/subscribers","subscription_url":"https://api.github.com/repos/tempesta-tech/tempesta/subscription","commits_url":"https://api.github.com/repos/tempesta-tech/tempesta/commits{/sha}","git_commits_url":"https://api.github.com/repos/tempesta-tech/tempesta/git/commits{/sha}","comments_url":"https://api.github.com/repos/tempesta-tech/tempesta/comments{/number}","issue_comment_url":"https://api.github.com/repos/tempesta-tech/tempesta/issues/comments{/number}","contents_url":"https://api.github.com/repos/tempesta-tech/tempesta/contents/{+path}","compare_url":"https://api.github.com/repos/tempesta-tech/tempesta/compare/{base}...{head}","merges_url":"https://api.github.com/repos/tempesta-tech/tempesta/merges","archive_url":"https://api.github.com/repos/tempesta-tech/tempesta/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/tempesta-tech/tempesta/downloads","issues_url":"https://api.github.com/repos/tempesta-tech/tempesta/issues{/number}","pulls_url":"https://api.github.com/repos/tempesta-tech/tempesta/pulls{/number}","milestones_url":"https://api.github.com/repos/tempesta-tech/tempesta/milestones{/number}","notifications_url":"https://api.github.com/repos/tempesta-tech/tempesta/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/tempesta-tech/tempesta/labels{/name}","releases_url":"https://api.github.com/repos/tempesta-tech/tempesta/releases{/id}","deployments_url":"https://api.github.com/repos/tempesta-tech/tempesta/deployments","created_at":"2014-08-19T18:44:05Z","updated_at":"2016-06-02T17:30:57Z","pushed_at":"2016-06-16T16:09:51Z","git_url":"git://github.com/tempesta-tech/tempesta.git","ssh_url":"git@github.com:tempesta-tech/tempesta.git","clone_url":"https://github.com/tempesta-tech/tempesta.git","svn_url":"https://github.com/tempesta-tech/tempesta","homepage":"","size":6779,"stargazers_count":110,"watchers_count":110,"language":"C","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":24,"mirror_url":null,"open_issues_count":102,"forks":24,"open_issues":102,"watchers":110,"default_branch":"master"}},"base":{"label":"tempesta-tech:master","ref":"master","sha":"453ac262acc65bb6546fca939bd5bcb6a9a71524","user":{"login":"tempesta-tech","id":10939672,"avatar_url":"https://avatars.githubusercontent.com/u/10939672?v=3","gravatar_id":"","url":"https://api.github.com/users/tempesta-tech","html_url":"https://github.com/tempesta-tech","followers_url":"https://api.github.com/users/tempesta-tech/followers","following_url":"https://api.github.com/users/tempesta-tech/following{/other_user}","gists_url":"https://api.github.com/users/tempesta-tech/gists{/gist_id}","starred_url":"https://api.github.com/users/tempesta-tech/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tempesta-tech/subscriptions","organizations_url":"https://api.github.com/users/tempesta-tech/orgs","repos_url":"https://api.github.com/users/tempesta-tech/repos","events_url":"https://api.github.com/users/tempesta-tech/events{/privacy}","received_events_url":"https://api.github.com/users/tempesta-tech/received_events","type":"Organization","site_admin":false},"repo":{"id":23121600,"name":"tempesta","full_name":"tempesta-tech/tempesta","owner":{"login":"tempesta-tech","id":10939672,"avatar_url":"https://avatars.githubusercontent.com/u/10939672?v=3","gravatar_id":"","url":"https://api.github.com/users/tempesta-tech","html_url":"https://github.com/tempesta-tech","followers_url":"https://api.github.com/users/tempesta-tech/followers","following_url":"https://api.github.com/users/tempesta-tech/following{/other_user}","gists_url":"https://api.github.com/users/tempesta-tech/gists{/gist_id}","starred_url":"https://api.github.com/users/tempesta-tech/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tempesta-tech/subscriptions","organizations_url":"https://api.github.com/users/tempesta-tech/orgs","repos_url":"https://api.github.com/users/tempesta-tech/repos","events_url":"https://api.github.com/users/tempesta-tech/events{/privacy}","received_events_url":"https://api.github.com/users/tempesta-tech/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/tempesta-tech/tempesta","description":"High performance HTTP accelerator and firewall for WAF and DDoS prevention","fork":false,"url":"https://api.github.com/repos/tempesta-tech/tempesta","forks_url":"https://api.github.com/repos/tempesta-tech/tempesta/forks","keys_url":"https://api.github.com/repos/tempesta-tech/tempesta/keys{/key_id}","collaborators_url":"https://api.github.com/repos/tempesta-tech/tempesta/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/tempesta-tech/tempesta/teams","hooks_url":"https://api.github.com/repos/tempesta-tech/tempesta/hooks","issue_events_url":"https://api.github.com/repos/tempesta-tech/tempesta/issues/events{/number}","events_url":"https://api.github.com/repos/tempesta-tech/tempesta/events","assignees_url":"https://api.github.com/repos/tempesta-tech/tempesta/assignees{/user}","branches_url":"https://api.github.com/repos/tempesta-tech/tempesta/branches{/branch}","tags_url":"https://api.github.com/repos/tempesta-tech/tempesta/tags","blobs_url":"https://api.github.com/repos/tempesta-tech/tempesta/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/tempesta-tech/tempesta/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/tempesta-tech/tempesta/git/refs{/sha}","trees_url":"https://api.github.com/repos/tempesta-tech/tempesta/git/trees{/sha}","statuses_url":"https://api.github.com/repos/tempesta-tech/tempesta/statuses/{sha}","languages_url":"https://api.github.com/repos/tempesta-tech/tempesta/languages","stargazers_url":"https://api.github.com/repos/tempesta-tech/tempesta/stargazers","contributors_url":"https://api.github.com/repos/tempesta-tech/tempesta/contributors","subscribers_url":"https://api.github.com/repos/tempesta-tech/tempesta/subscribers","subscription_url":"https://api.github.com/repos/tempesta-tech/tempesta/subscription","commits_url":"https://api.github.com/repos/tempesta-tech/tempesta/commits{/sha}","git_commits_url":"https://api.github.com/repos/tempesta-tech/tempesta/git/commits{/sha}","comments_url":"https://api.github.com/repos/tempesta-tech/tempesta/comments{/number}","issue_comment_url":"https://api.github.com/repos/tempesta-tech/tempesta/issues/comments{/number}","contents_url":"https://api.github.com/repos/tempesta-tech/tempesta/contents/{+path}","compare_url":"https://api.github.com/repos/tempesta-tech/tempesta/compare/{base}...{head}","merges_url":"https://api.github.com/repos/tempesta-tech/tempesta/merges","archive_url":"https://api.github.com/repos/tempesta-tech/tempesta/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/tempesta-tech/tempesta/downloads","issues_url":"https://api.github.com/repos/tempesta-tech/tempesta/issues{/number}","pulls_url":"https://api.github.com/repos/tempesta-tech/tempesta/pulls{/number}","milestones_url":"https://api.github.com/repos/tempesta-tech/tempesta/milestones{/number}","notifications_url":"https://api.github.com/repos/tempesta-tech/tempesta/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/tempesta-tech/tempesta/labels{/name}","releases_url":"https://api.github.com/repos/tempesta-tech/tempesta/releases{/id}","deployments_url":"https://api.github.com/repos/tempesta-tech/tempesta/deployments","created_at":"2014-08-19T18:44:05Z","updated_at":"2016-06-02T17:30:57Z","pushed_at":"2016-06-16T16:09:51Z","git_url":"git://github.com/tempesta-tech/tempesta.git","ssh_url":"git@github.com:tempesta-tech/tempesta.git","clone_url":"https://github.com/tempesta-tech/tempesta.git","svn_url":"https://github.com/tempesta-tech/tempesta","homepage":"","size":6779,"stargazers_count":110,"watchers_count":110,"language":"C","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":24,"mirror_url":null,"open_issues_count":102,"forks":24,"open_issues":102,"watchers":110,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/tempesta-tech/tempesta/pulls/557"},"html":{"href":"https://github.com/tempesta-tech/tempesta/pull/557"},"issue":{"href":"https://api.github.com/repos/tempesta-tech/tempesta/issues/557"},"comments":{"href":"https://api.github.com/repos/tempesta-tech/tempesta/issues/557/comments"},"review_comments":{"href":"https://api.github.com/repos/tempesta-tech/tempesta/pulls/557/comments"},"review_comment":{"href":"https://api.github.com/repos/tempesta-tech/tempesta/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/tempesta-tech/tempesta/pulls/557/commits"},"statuses":{"href":"https://api.github.com/repos/tempesta-tech/tempesta/statuses/4ec7d53ee8af0a33c830f914b6da6e7b8617b83f"}}}}
{"actor":{"display_login":"krizhanovsky"}}