| Message ID | 145663616977.3865.9772784012366988314.stgit@notabene (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
U28gYmFzZWQgb24gdGhlIGJvdHRvbSB0d28gYml0cywgd2UgY2FuIHRlbGwgd2hhdCB0aGlzIGVu dHJ5IGlzOg0KDQowMCAtIGRhdGEgcG9pbnRlcg0KMDEgLSBpbmRpcmVjdCBlbnRyeSAocG9pbnRl ciB0byBhbm90aGVyIGxldmVsIG9mIHRoZSByYWRpeCB0cmVlKQ0KMTAgLSBleGNlcHRpb25hbCBl bnRyeQ0KMTEgLSBsb2NrZWQgZXhjZXB0aW9uYWwgZW50cnkNCg0KSSB3YXMgY29uY2VybmVkIHRo YXQgdGhpcyBwYXRjaCB3b3VsZCBjbGFzaCB3aXRoIHRoZSBzdXBwb3J0IGZvciBtdWx0aS1vcmRl ciBlbnRyaWVzIGluIHRoZSByYWRpeCB0cmVlLCBidXQgYWZ0ZXIgc29tZSB0aG91Z2h0LCBJIG5v dyBiZWxpZXZlIHRoYXQgaXQgZG9lc24ndC4gIFRoZSBtdWx0aS1vcmRlciBlbnRyaWVzIGNoYW5n ZXMgcGVybWl0IGZpbmRpbmcgZGF0YSBwb2ludGVycyBvciBleGNlcHRpb25hbCBlbnRyaWVzIGlu IHRoZSB0cmVlIHdoZXJlIGJlZm9yZSBvbmx5IGluZGlyZWN0IGVudHJpZXMgY291bGQgYmUgZm91 bmQsIGJ1dCB3aXRoIHRoZSBjaGFuZ2VzIHRvIHJhZGl4X3RyZWVfaXNfaW5kaXJlY3RfcHRyIGJl bG93LCBldmVyeXRoaW5nIHNob3VsZCB3b3JrIGZpbmUuDQoNCi0tLS0tT3JpZ2luYWwgTWVzc2Fn ZS0tLS0tDQpGcm9tOiBOZWlsQnJvd24gW21haWx0bzpuZWlsYkBzdXNlLmNvbV0gDQpTZW50OiBT YXR1cmRheSwgRmVicnVhcnkgMjcsIDIwMTYgOTowOSBQTQ0KVG86IFJvc3MgWndpc2xlcjsgV2ls Y294LCBNYXR0aGV3IFI7IEFuZHJldyBNb3J0b247IEphbiBLYXJhDQpDYzogbGludXgta2VybmVs QHZnZXIua2VybmVsLm9yZzsgbGludXgtZnNkZXZlbEB2Z2VyLmtlcm5lbC5vcmc7IGxpbnV4LW1t QGt2YWNrLm9yZw0KU3ViamVjdDogW1BBVENIIDIvM10gcmFkaXgtdHJlZTogbWFrZSAnaW5kaXJl Y3QnIGJpdCBhdmFpbGFibGUgdG8gZXhjZXB0aW9uIGVudHJpZXMuDQoNCkEgcG9pbnRlciB0byBh IHJhZGl4X3RyZWVfbm9kZSB3aWxsIGFsd2F5cyBoYXZlIHRoZSAnZXhjZXB0aW9uJw0KYml0IGNs ZWFyZWQsIHNvIGlmIHRoZSBleGNlcHRpb24gYml0IGlzIHNldCB0aGUgdmFsdWUgY2Fubm90DQpi ZSBhbiBpbmRpcmVjdCBwb2ludGVyLiAgVGh1cyBpdCBpcyBzYWZlIHRvIG1ha2UgdGhlICdpbmRp cmVjdCBiaXQnDQphdmFpbGFibGUgdG8gc3RvcmUgZXh0cmEgaW5mb3JtYXRpb24gaW4gZXhjZXB0 aW9uIGVudHJpZXMuDQoNClRoaXMgcGF0Y2ggYWRkcyBhICdQVFJfTUFTSycgYW5kIGEgdmFsdWUg aXMgb25seSB0cmVhdGVkIGFzDQphbiBpbmRpcmVjdCAocG9pbnRlcikgZW50cnkgdGhlIDIgbHMt Yml0cyBhcmUgJzAxJy4NCg0KVGhlIGNoYW5nZSBpbiByYWRpeC10cmVlLmMgZW5zdXJlcyB0aGUg c3RvcmVkIHZhbHVlIHN0aWxsIGxvb2tzIGxpa2UgYW4NCmluZGlyZWN0IHBvaW50ZXIsIGFuZCBz YXZlcyBhIGxvYWQgYXMgd2VsbC4NCg0KV2UgY291bGQgc3dhcCB0aGUgdHdvIGJpdHMgYW5kIHNv IGtlZXAgYWxsIHRoZSBleGVjdGlvbmFsIGJpdHMgY29udGlnaW91cy4NCkJ1dCBJIGhhdmUgb3Ro ZXIgcGxhbnMgZm9yIHRoYXQgYml0Li4uLg0KDQpTaWduZWQtb2ZmLWJ5OiBOZWlsQnJvd24gPG5l aWxiQHN1c2UuY29tPg0KLS0tDQogaW5jbHVkZS9saW51eC9yYWRpeC10cmVlLmggfCAgIDExICsr KysrKysrKy0tDQogbGliL3JhZGl4LXRyZWUuYyAgICAgICAgICAgfCAgICAyICstDQogMiBmaWxl cyBjaGFuZ2VkLCAxMCBpbnNlcnRpb25zKCspLCAzIGRlbGV0aW9ucygtKQ0KDQpkaWZmIC0tZ2l0 IGEvaW5jbHVkZS9saW51eC9yYWRpeC10cmVlLmggYi9pbmNsdWRlL2xpbnV4L3JhZGl4LXRyZWUu aA0KaW5kZXggOTY4MTUwYWI4YTFjLi40NTBjMTJiNTQ2YjcgMTAwNjQ0DQotLS0gYS9pbmNsdWRl L2xpbnV4L3JhZGl4LXRyZWUuaA0KKysrIGIvaW5jbHVkZS9saW51eC9yYWRpeC10cmVlLmgNCkBA IC00MCw4ICs0MCwxMyBAQA0KICAqIEluZGlyZWN0IHBvaW50ZXIgaW4gZmFjdCBpcyBhbHNvIHVz ZWQgdG8gdGFnIHRoZSBsYXN0IHBvaW50ZXIgb2YgYSBub2RlDQogICogd2hlbiBpdCBpcyBzaHJ1 bmssIGJlZm9yZSB3ZSByY3UgZnJlZSB0aGUgbm9kZS4gU2VlIHNocmluayBjb2RlIGZvcg0KICAq IGRldGFpbHMuDQorICoNCisgKiBUbyBhbGxvdyBhbiBleGNlcHRpb24gZW50cnkgdG8gb25seSBs b3NlIG9uZSBiaXQsIHdlIGlnbm9yZQ0KKyAqIHRoZSBJTkRJUkVDVCBiaXQgd2hlbiB0aGUgZXhj ZXB0aW9uIGJpdCBpcyBzZXQuICBTbyBhbiBlbnRyeSBpcw0KKyAqIGluZGlyZWN0IGlmIHRoZSBs ZWFzdCBzaWduaWZpY2FudCAyIGJpdHMgYXJlIDAxLg0KICAqLw0KICNkZWZpbmUgUkFESVhfVFJF RV9JTkRJUkVDVF9QVFIJCTENCisjZGVmaW5lIFJBRElYX1RSRUVfSU5ESVJFQ1RfTUFTSwkzDQog LyoNCiAgKiBBIGNvbW1vbiB1c2Ugb2YgdGhlIHJhZGl4IHRyZWUgaXMgdG8gc3RvcmUgcG9pbnRl cnMgdG8gc3RydWN0IHBhZ2VzOw0KICAqIGJ1dCBzaG1lbS90bXBmcyBuZWVkcyBhbHNvIHRvIHN0 b3JlIHN3YXAgZW50cmllcyBpbiB0aGUgc2FtZSB0cmVlOg0KQEAgLTUzLDcgKzU4LDggQEANCiAN CiBzdGF0aWMgaW5saW5lIGludCByYWRpeF90cmVlX2lzX2luZGlyZWN0X3B0cih2b2lkICpwdHIp DQogew0KLQlyZXR1cm4gKGludCkoKHVuc2lnbmVkIGxvbmcpcHRyICYgUkFESVhfVFJFRV9JTkRJ UkVDVF9QVFIpOw0KKwlyZXR1cm4gKCh1bnNpZ25lZCBsb25nKXB0ciAmIFJBRElYX1RSRUVfSU5E SVJFQ1RfTUFTSykNCisJCT09IFJBRElYX1RSRUVfSU5ESVJFQ1RfUFRSOw0KIH0NCiANCiAvKioq IHJhZGl4LXRyZWUgQVBJIHN0YXJ0cyBoZXJlICoqKi8NCkBAIC0yMjEsNyArMjI3LDggQEAgc3Rh dGljIGlubGluZSB2b2lkICpyYWRpeF90cmVlX2RlcmVmX3Nsb3RfcHJvdGVjdGVkKHZvaWQgKipw c2xvdCwNCiAgKi8NCiBzdGF0aWMgaW5saW5lIGludCByYWRpeF90cmVlX2RlcmVmX3JldHJ5KHZv aWQgKmFyZykNCiB7DQotCXJldHVybiB1bmxpa2VseSgodW5zaWduZWQgbG9uZylhcmcgJiBSQURJ WF9UUkVFX0lORElSRUNUX1BUUik7DQorCXJldHVybiB1bmxpa2VseSgoKHVuc2lnbmVkIGxvbmcp YXJnICYgUkFESVhfVFJFRV9JTkRJUkVDVF9NQVNLKQ0KKwkJCT09IFJBRElYX1RSRUVfSU5ESVJF Q1RfUFRSKTsNCiB9DQogDQogLyoqDQpkaWZmIC0tZ2l0IGEvbGliL3JhZGl4LXRyZWUuYyBiL2xp Yi9yYWRpeC10cmVlLmMNCmluZGV4IDZiNzllOTAyNmUyNC4uMzdkNDY0M2FiNWMwIDEwMDY0NA0K LS0tIGEvbGliL3JhZGl4LXRyZWUuYw0KKysrIGIvbGliL3JhZGl4LXRyZWUuYw0KQEAgLTEzMDUs NyArMTMwNSw3IEBAIHN0YXRpYyBpbmxpbmUgdm9pZCByYWRpeF90cmVlX3NocmluayhzdHJ1Y3Qg cmFkaXhfdHJlZV9yb290ICpyb290KQ0KIAkJICogdG8gZm9yY2UgY2FsbGVycyB0byByZXRyeS4N CiAJCSAqLw0KIAkJaWYgKHJvb3QtPmhlaWdodCA9PSAwKQ0KLQkJCSooKHVuc2lnbmVkIGxvbmcg KikmdG9fZnJlZS0+c2xvdHNbMF0pIHw9DQorCQkJKigodW5zaWduZWQgbG9uZyAqKSZ0b19mcmVl LT5zbG90c1swXSkgPQ0KIAkJCQkJCVJBRElYX1RSRUVfSU5ESVJFQ1RfUFRSOw0KIA0KIAkJcmFk aXhfdHJlZV9ub2RlX2ZyZWUodG9fZnJlZSk7DQoNCg0K -- To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Mon, Feb 29, 2016 at 02:41:55PM +0000, Wilcox, Matthew R wrote: > So based on the bottom two bits, we can tell what this entry is: > > 00 - data pointer > 01 - indirect entry (pointer to another level of the radix tree) > 10 - exceptional entry > 11 - locked exceptional entry > > I was concerned that this patch would clash with the support for multi-order > entries in the radix tree, but after some thought, I now believe that it > doesn't. The multi-order entries changes permit finding data pointers or > exceptional entries in the tree where before only indirect entries could be > found, but with the changes to radix_tree_is_indirect_ptr below, everything > should work fine. Yep, this seems workable to me. > -----Original Message----- > From: NeilBrown [mailto:neilb@suse.com] > Sent: Saturday, February 27, 2016 9:09 PM > To: Ross Zwisler; Wilcox, Matthew R; Andrew Morton; Jan Kara > Cc: linux-kernel@vger.kernel.org; linux-fsdevel@vger.kernel.org; linux-mm@kvack.org > Subject: [PATCH 2/3] radix-tree: make 'indirect' bit available to exception entries. > > A pointer to a radix_tree_node will always have the 'exception' > bit cleared, so if the exception bit is set the value cannot > be an indirect pointer. Thus it is safe to make the 'indirect bit' > available to store extra information in exception entries. > > This patch adds a 'PTR_MASK' and a value is only treated as > an indirect (pointer) entry the 2 ls-bits are '01'. > > The change in radix-tree.c ensures the stored value still looks like an > indirect pointer, and saves a load as well. > > We could swap the two bits and so keep all the exectional bits contigious. > But I have other plans for that bit.... > > Signed-off-by: NeilBrown <neilb@suse.com> > --- > include/linux/radix-tree.h | 11 +++++++++-- > lib/radix-tree.c | 2 +- > 2 files changed, 10 insertions(+), 3 deletions(-) > > diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h > index 968150ab8a1c..450c12b546b7 100644 > --- a/include/linux/radix-tree.h > +++ b/include/linux/radix-tree.h > @@ -40,8 +40,13 @@ > * Indirect pointer in fact is also used to tag the last pointer of a node > * when it is shrunk, before we rcu free the node. See shrink code for > * details. > + * > + * To allow an exception entry to only lose one bit, we ignore > + * the INDIRECT bit when the exception bit is set. So an entry is > + * indirect if the least significant 2 bits are 01. > */ > #define RADIX_TREE_INDIRECT_PTR 1 > +#define RADIX_TREE_INDIRECT_MASK 3 > /* > * A common use of the radix tree is to store pointers to struct pages; > * but shmem/tmpfs needs also to store swap entries in the same tree: > @@ -53,7 +58,8 @@ > > static inline int radix_tree_is_indirect_ptr(void *ptr) > { > - return (int)((unsigned long)ptr & RADIX_TREE_INDIRECT_PTR); > + return ((unsigned long)ptr & RADIX_TREE_INDIRECT_MASK) > + == RADIX_TREE_INDIRECT_PTR; > } > > /*** radix-tree API starts here ***/ > @@ -221,7 +227,8 @@ static inline void *radix_tree_deref_slot_protected(void **pslot, > */ > static inline int radix_tree_deref_retry(void *arg) > { > - return unlikely((unsigned long)arg & RADIX_TREE_INDIRECT_PTR); > + return unlikely(((unsigned long)arg & RADIX_TREE_INDIRECT_MASK) > + == RADIX_TREE_INDIRECT_PTR); > } > > /** > diff --git a/lib/radix-tree.c b/lib/radix-tree.c > index 6b79e9026e24..37d4643ab5c0 100644 > --- a/lib/radix-tree.c > +++ b/lib/radix-tree.c > @@ -1305,7 +1305,7 @@ static inline void radix_tree_shrink(struct radix_tree_root *root) > * to force callers to retry. > */ > if (root->height == 0) > - *((unsigned long *)&to_free->slots[0]) |= > + *((unsigned long *)&to_free->slots[0]) = > RADIX_TREE_INDIRECT_PTR; > > radix_tree_node_free(to_free); > > -- To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h index 968150ab8a1c..450c12b546b7 100644 --- a/include/linux/radix-tree.h +++ b/include/linux/radix-tree.h @@ -40,8 +40,13 @@ * Indirect pointer in fact is also used to tag the last pointer of a node * when it is shrunk, before we rcu free the node. See shrink code for * details. + * + * To allow an exception entry to only lose one bit, we ignore + * the INDIRECT bit when the exception bit is set. So an entry is + * indirect if the least significant 2 bits are 01. */ #define RADIX_TREE_INDIRECT_PTR 1 +#define RADIX_TREE_INDIRECT_MASK 3 /* * A common use of the radix tree is to store pointers to struct pages; * but shmem/tmpfs needs also to store swap entries in the same tree: @@ -53,7 +58,8 @@ static inline int radix_tree_is_indirect_ptr(void *ptr) { - return (int)((unsigned long)ptr & RADIX_TREE_INDIRECT_PTR); + return ((unsigned long)ptr & RADIX_TREE_INDIRECT_MASK) + == RADIX_TREE_INDIRECT_PTR; } /*** radix-tree API starts here ***/ @@ -221,7 +227,8 @@ static inline void *radix_tree_deref_slot_protected(void **pslot, */ static inline int radix_tree_deref_retry(void *arg) { - return unlikely((unsigned long)arg & RADIX_TREE_INDIRECT_PTR); + return unlikely(((unsigned long)arg & RADIX_TREE_INDIRECT_MASK) + == RADIX_TREE_INDIRECT_PTR); } /** diff --git a/lib/radix-tree.c b/lib/radix-tree.c index 6b79e9026e24..37d4643ab5c0 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -1305,7 +1305,7 @@ static inline void radix_tree_shrink(struct radix_tree_root *root) * to force callers to retry. */ if (root->height == 0) - *((unsigned long *)&to_free->slots[0]) |= + *((unsigned long *)&to_free->slots[0]) = RADIX_TREE_INDIRECT_PTR; radix_tree_node_free(to_free);
A pointer to a radix_tree_node will always have the 'exception' bit cleared, so if the exception bit is set the value cannot be an indirect pointer. Thus it is safe to make the 'indirect bit' available to store extra information in exception entries. This patch adds a 'PTR_MASK' and a value is only treated as an indirect (pointer) entry the 2 ls-bits are '01'. The change in radix-tree.c ensures the stored value still looks like an indirect pointer, and saves a load as well. We could swap the two bits and so keep all the exectional bits contigious. But I have other plans for that bit.... Signed-off-by: NeilBrown <neilb@suse.com> --- include/linux/radix-tree.h | 11 +++++++++-- lib/radix-tree.c | 2 +- 2 files changed, 10 insertions(+), 3 deletions(-) -- To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html