From: Paul Davies <pauld@gelato.unsw.edu.au>
To: linux-mm@kvack.org
Cc: Paul Davies <pauld@gelato.unsw.edu.au>
Subject: [PATCH 10/12] Alternate page table implementation cont...
Date: Sat, 13 Jan 2007 13:49:33 +1100 [thread overview]
Message-ID: <20070113024933.29682.30267.sendpatchset@weill.orchestra.cse.unsw.EDU.AU> (raw)
In-Reply-To: <20070113024540.29682.27024.sendpatchset@weill.orchestra.cse.unsw.EDU.AU>
PATCH GPT 10
* Continue adding GPT implementation
Signed-Off-By: Paul Davies <pauld@gelato.unsw.edu.au>
---
pt-gpt-core.c | 219 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 219 insertions(+)
Index: linux-2.6.20-rc1/mm/pt-gpt-core.c
===================================================================
--- linux-2.6.20-rc1.orig/mm/pt-gpt-core.c 2007-01-03 15:57:35.539309000 +1100
+++ linux-2.6.20-rc1/mm/pt-gpt-core.c 2007-01-03 16:07:14.297584000 +1100
@@ -600,3 +600,222 @@
gpt_iterator_inspect_push_range(iterator_u);
return 0;
}
+
+static inline void
+gpt_iterator_terminal_free_pgtables(gpt_iterator_t* iterator_u)
+{
+ int8_t replication;
+
+ if(gpt_iterator_check_bounds(iterator_u, &replication) ==
+ GPT_ITERATOR_LIMIT) {
+ if(iterator_u->depth == 0) {
+ iterator_u->node_p = NULL;
+ return;
+ }
+ iterator_u->finished = 1;
+ gpt_iterator_inspect_pop(iterator_u);
+ } else {
+ gpt_iterator_inspect_next(iterator_u, replication);
+ }
+}
+
+static inline int
+gpt_iterator_internal_visit_range(gpt_iterator_t* iterator_u,
+ gpt_node_t** node_p_r)
+{
+ //int8_t replication;
+
+ panic("Unimplemented!");
+ if(iterator_u->finished) {
+ gpt_iterator_return(*iterator_u, NULL, node_p_r);
+ gpt_iterator_inspect_next(iterator_u, 0);
+ return 1;
+ }
+ //gpt_iterator_check_bounds(iterator_u,
+}
+
+static inline int
+gpt_iterator_internal_visit_all(gpt_iterator_t* iterator_u, gpt_key_t* key_r,
+ gpt_node_t** node_p_r)
+{
+ int8_t replication;
+
+ /* Process node once children have been processed. */
+ if(iterator_u->finished) {
+ gpt_iterator_return(*iterator_u, key_r, node_p_r);
+ gpt_iterator_inspect_next(iterator_u, 0);
+ return 1;
+ }
+ gpt_iterator_check_bounds(iterator_u, &replication); // updates key.
+ /* If guard is in range process child nodes if guard. */
+ gpt_iterator_inspect_push_range(iterator_u);
+ return 0;
+}
+
+static inline void
+gpt_iterator_internal_skip_range(gpt_iterator_t* iterator_u)
+{
+ int8_t replication;
+
+ /* Process node once children have been processed. */
+ if(iterator_u->finished) {
+ gpt_iterator_inspect_next(iterator_u, 0);
+ return;
+ }
+ /* If guard is in range process child nodes if guard. */
+ switch(gpt_iterator_check_bounds(iterator_u, &replication)) {
+ case GPT_ITERATOR_INRANGE:
+ gpt_iterator_inspect_push_range(iterator_u);
+ break;
+ case GPT_ITERATOR_START:
+ BUG_ON(replication != 0); // Internal nodes not be replicated.
+ gpt_iterator_inspect_next(iterator_u, 0);
+ break;
+ case GPT_ITERATOR_LIMIT:
+ iterator_u->node_p = NULL;
+ break;
+ default:
+ panic("Should never get here!");
+ }
+}
+
+static inline void
+gpt_iterator_terminal_skip_range(gpt_iterator_t* iterator_u)
+{
+ int8_t replication;
+
+ switch(gpt_iterator_check_bounds(iterator_u, &replication)) {
+ case GPT_ITERATOR_INRANGE:
+ case GPT_ITERATOR_START:
+ gpt_iterator_inspect_next(iterator_u, replication);
+ break;
+ case GPT_ITERATOR_LIMIT:
+ iterator_u->node_p = NULL;
+ break;
+ default:
+ panic("Should never get here!");
+ }
+}
+
+static inline void
+gpt_iterator_terminal_skip_all(gpt_iterator_t* iterator_u)
+{
+ int8_t replication;
+
+ // awiggins (2006-09-14) Should actually check replication of leaves.
+ gpt_iterator_check_bounds(iterator_u, &replication); // updates key.
+ gpt_iterator_inspect_next(iterator_u, replication);
+}
+
+
+static inline int
+gpt_iterator_check_bounds(gpt_iterator_t* iterator_u, int8_t* replication_r)
+{
+ int8_t coverage;
+ gpt_key_t key;
+ gpt_key_value_t key_value;
+
+ /* Construct the search-key for the current node. */
+ coverage = iterator_u->coverage - gpt_key_read_length(iterator_u->key);
+ *replication_r = gptNodeReplication(*iterator_u->node_p, coverage);
+ key = gpt_node_read_guard(gpt_node_get(iterator_u->node_p));
+ key = gpt_keys_merge_LSB(iterator_u->key, key);
+ iterator_u->key = key = gpt_key_cut_LSB(*replication_r, key);
+ /* Compare the current nodes search-key to the iterator's range. */
+ key_value = gpt_key_read_value(key);
+ coverage = iterator_u->coverage - gpt_key_read_length(key);
+ if(key_value < (iterator_u->start >> coverage)) {
+ return GPT_ITERATOR_START;
+ }
+ if(key_value > (iterator_u->limit >> coverage)) {
+ return GPT_ITERATOR_LIMIT;
+ }
+ return GPT_ITERATOR_INRANGE;
+}
+
+static inline void
+gpt_iterator_inspect_push_range(gpt_iterator_t* iterator_u)
+{
+ int8_t key_length, coverage, level_order;
+ gpt_key_t index;
+ gpt_node_t node, *level;
+ gpt_key_value_t i, key_value;
+
+ /* Get details of next level. */
+ node = gpt_node_get(iterator_u->node_p);
+ level = gpt_node_internal_read_ptr(node);
+ level_order = gpt_node_internal_read_order(node);
+ /* Find index into next level. */
+ key_value = gpt_key_read_value(iterator_u->key);
+ key_length = gpt_key_read_length(iterator_u->key);
+ coverage = iterator_u->coverage - key_length;
+ i = iterator_u->start >> (coverage - level_order);
+ if((i >> level_order) == (key_value)) {
+ i &= ~gpt_key_value_mask(level_order);
+ } else {
+ i = 0;
+ }
+ index = gpt_key_init(i, level_order);
+ /* Update iterator position. */
+ iterator_u->stack[(iterator_u->depth)++] = iterator_u->node_p;
+ iterator_u->node_p = level + i;
+ iterator_u->key = gpt_keys_merge_MSB(index, iterator_u->key);
+}
+
+static inline void
+gpt_iterator_inspect_push_all(gpt_iterator_t* iterator_u)
+{
+ int8_t level_order;
+ gpt_key_t index;
+ gpt_node_t node, *level;
+
+ /* Get details of next level. */
+ node = gpt_node_get(iterator_u->node_p);
+ level = gpt_node_internal_read_ptr(node);
+ level_order = gpt_node_internal_read_order(node);
+ /* Update iterator position. */
+ index = gpt_key_init(0, level_order);
+ iterator_u->stack[(iterator_u->depth)++] = iterator_u->node_p;
+ iterator_u->node_p = level;
+ iterator_u->key = gpt_keys_merge_MSB(index, iterator_u->key);
+}
+
+static inline void
+gpt_iterator_inspect_next(gpt_iterator_t* iterator_u, int8_t replication)
+{
+ int8_t level_order, key_length;
+ gpt_key_t guard, index;
+ gpt_node_t node, *level;
+ gpt_key_value_t i, step;
+
+ /* The root node has no siblings, iteration complete. */
+ if(iterator_u->depth == 0) {
+ iterator_u->node_p = NULL;
+ return;
+ }
+ /* Strip the current nodes guard bits from the key. */
+ node = gpt_node_get(iterator_u->node_p);
+ if(gpt_node_valid(node)) {
+ guard = gpt_node_read_guard(node);
+ key_length = gpt_key_read_length(guard);
+ iterator_u->key = gpt_key_cut_LSB(key_length, iterator_u->key);
+ }
+ /* Update index and either get next sibling or return to parent. */
+ node = gpt_node_get(gpt_iterator_parent(*iterator_u));
+ level = gpt_node_internal_read_ptr(node);
+ level_order = gpt_node_internal_read_order(node);
+ index = gpt_key_cut_LSB2(level_order - replication, &(iterator_u->key));
+ i = gpt_key_read_value(index);
+ key_length = gpt_key_read_length(index);
+ step = 1 << replication;
+ if(i < ((1 << (level_order - replication)) - 1)) {
+ i = (i + 1) << replication;
+ index = gpt_key_init(i, level_order);
+ iterator_u->key = gpt_keys_merge_MSB(index, iterator_u->key);
+ iterator_u->node_p = level + i;
+ iterator_u->finished = 0;
+ } else {
+ gpt_iterator_inspect_pop(iterator_u);
+ }
+}
+
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
next prev parent reply other threads:[~2007-01-13 2:49 UTC|newest]
Thread overview: 60+ messages / expand[flat|nested] mbox.gz Atom feed top
2007-01-13 2:45 [PATCH 0/29] Page Table Interface Explanation Paul Davies
2007-01-13 2:45 ` [PATCH 1/29] Abstract current page table implementation Paul Davies
2007-01-13 2:45 ` [PATCH 2/29] " Paul Davies
2007-01-13 2:45 ` [PATCH 3/29] " Paul Davies
2007-01-16 18:55 ` Christoph Lameter
2007-01-13 2:46 ` [PATCH 4/29] Introduce Page Table Interface (PTI) Paul Davies
2007-01-16 19:02 ` Christoph Lameter
2007-01-13 2:46 ` [PATCH 5/29] Start calling simple PTI functions Paul Davies
2007-01-16 19:04 ` Christoph Lameter
2007-01-18 6:43 ` Paul Cameron Davies
2007-01-13 2:46 ` [PATCH 6/29] Tweak IA64 arch dependent files to work with PTI Paul Davies
2007-01-16 19:05 ` Christoph Lameter
2007-01-13 2:46 ` [PATCH 7/29] Continue calling simple PTI functions Paul Davies
2007-01-16 19:08 ` Christoph Lameter
2007-01-13 2:46 ` [PATCH 8/29] Clean up page fault handers Paul Davies
2007-01-13 2:46 ` [PATCH 9/29] Clean up page fault handlers Paul Davies
2007-01-13 2:46 ` [PATCH 10/29] Call simple PTI functions Paul Davies
2007-01-13 2:46 ` [PATCH 11/29] Call simple PTI functions cont Paul Davies
2007-01-13 2:46 ` [PATCH 12/29] Abstract page table tear down Paul Davies
2007-01-13 2:46 ` [PATCH 13/29] Finish abstracting " Paul Davies
2007-01-13 2:46 ` [PATCH 14/29] Abstract copy page range iterator Paul Davies
2007-01-13 2:46 ` [PATCH 15/29] Finish abstracting copy page range Paul Davies
2007-01-13 2:47 ` [PATCH 16/29] Abstract unmap page range iterator Paul Davies
2007-01-13 2:47 ` [PATCH 17/29] Finish abstracting unmap page range Paul Davies
2007-01-13 2:47 ` [PATCH 18/29] Abstract zeromap " Paul Davies
2007-01-13 2:47 ` [PATCH 19/29] Abstract remap pfn range Paul Davies
2007-01-13 2:47 ` [PATCH 20/29] Abstract change protection iterator Paul Davies
2007-01-13 2:47 ` [PATCH 21/29] Abstract unmap vm area Paul Davies
2007-01-13 2:47 ` [PATCH 22/29] Abstract map " Paul Davies
2007-01-13 2:47 ` [PATCH 23/29] Abstract unuse_vma Paul Davies
2007-01-13 2:47 ` [PATCH 24/29] Abstract smaps iterator Paul Davies
2007-01-13 2:47 ` [PATCH 25/29] Abstact mempolicy iterator Paul Davies
2007-01-13 2:47 ` [PATCH 26/29] Abstract mempolicy iterator cont Paul Davies
2007-01-13 2:48 ` [PATCH 27/29] Abstract implementation dependent code for mremap Paul Davies
2007-01-13 2:48 ` [PATCH 28/29] Abstract ioremap iterator Paul Davies
2007-01-13 2:48 ` [PATCH 29/29] Tweak i386 arch dependent files to work with PTI Paul Davies
2007-01-13 2:48 ` [PATCH 1/5] Introduce IA64 page table interface Paul Davies
2007-01-13 2:48 ` [PATCH 2/5] Abstract pgtable Paul Davies
2007-01-13 2:48 ` [PATCH 3/5] Abstact pgtable continued Paul Davies
2007-01-13 2:48 ` [PATCH 4/5] Abstract assembler lookup Paul Davies
2007-01-13 2:48 ` [PATCH 5/5] Abstract pgalloc Paul Davies
2007-01-13 2:48 ` [PATCH 1/12] Alternate page table implementation (GPT) Paul Davies
2007-01-13 2:48 ` [PATCH 2/12] Alternate page table implementation cont Paul Davies
2007-01-13 2:48 ` [PATCH 3/12] " Paul Davies
2007-01-13 2:49 ` [PATCH 4/12] " Paul Davies
2007-01-13 2:49 ` [PATCH 5/12] " Paul Davies
2007-01-13 2:49 ` [PATCH 6/12] " Paul Davies
2007-01-13 2:49 ` [PATCH 7/12] " Paul Davies
2007-01-13 2:49 ` [PATCH 8/12] " Paul Davies
2007-01-13 2:49 ` [PATCH 9/12] " Paul Davies
2007-01-13 2:49 ` Paul Davies [this message]
2007-01-13 2:49 ` [PATCH 11/12] " Paul Davies
2007-01-13 2:49 ` [PATCH 12/12] " Paul Davies
2007-01-13 19:29 ` [PATCH 0/29] Page Table Interface Explanation Peter Zijlstra
2007-01-14 10:06 ` Paul Cameron Davies
2007-01-16 18:49 ` Christoph Lameter
2007-01-18 6:22 ` Paul Cameron Davies
2007-01-16 18:51 ` Christoph Lameter
2007-01-18 6:53 ` Paul Cameron Davies
2007-01-16 19:14 ` Christoph Lameter
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20070113024933.29682.30267.sendpatchset@weill.orchestra.cse.unsw.EDU.AU \
--to=pauld@gelato.unsw.edu.au \
--cc=linux-mm@kvack.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox