You are viewing a plain text version of this content. The canonical link for it is here.
Posted to jira@kafka.apache.org by "Claudenw (via GitHub)" <gi...@apache.org> on 2024/09/04 10:46:40 UTC
[PR] KAFKA-17423 Trie implementation [kafka]
Claudenw opened a new pull request, #17087:
URL: https://github.com/apache/kafka/pull/17087
This change is dependent upon KAFKA-17316: Standard authorizer refactor (#16779) That change will reduce the number of files that are changed in this request.
*More detailed description of your change,
if necessary. The PR title and PR message become
the squashed commit message, so use a separate
comment to ping reviewers.*
Implements the StandardAuthorizer with a Trie data structure instead of the original sorted list. This results in an order of magnitude speed increase.
Extensive tests are added to verify that the new implementation matches the old implementation.
*Summary of testing strategy (including rationale)
for the feature or bug fix. Unit and/or integration
tests are expected for any behaviour change and
system tests should be considered for larger changes.*
### Committer Checklist (excluded from commit message)
- [ ] Verify design and implementation
- [ ] Verify test coverage and CI build status
- [ ] Verify documentation (including upgrade notes)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: jira-unsubscribe@kafka.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] KAFKA-17423 Trie implementation [kafka]
Posted by "Claudenw (via GitHub)" <gi...@apache.org>.
Claudenw commented on code in PR #17087:
URL: https://github.com/apache/kafka/pull/17087#discussion_r1749198796
##########
metadata/src/main/java/org/apache/kafka/metadata/authorizer/bitmap/BitMaps.java:
##########
@@ -0,0 +1,159 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+
+package org.apache.kafka.metadata.authorizer.bitmap;
+
+
+/**
+ * Contains functions to convert {@code int} indices into Bitmap bit positions and visa versa.
+ *
+ * <p>The functions view an array of longs as a collection of bit maps each containing 64 bits. The bits are arranged
+ * in memory as a little-endian long value. </p>
+ *
+ * This code is based on the BitMaps code in Apache Commons Collections.
+ * @see <a href="https://commons.apache.org/proper//commons-collections/apidocs/org/apache/commons/collections4/bloomfilter/BitMaps.html">Apache Commons Collections Bitmaps</a>
+ */
+public class BitMaps {
+ /** A bit shift to apply to an integer to divided by 32 (2^5). */
+ private static final int DIVIDE_BY_32 = 5;
+
+ /**
+ * Checks if the specified index bit is enabled in the array of bit maps.
+ *
+ * If the bit specified by bitIndex is not in the bit map false is returned.
+ *
+ * @param bitMaps The array of bit maps.
+ * @param bitIndex the index of the bit to locate.
+ * @return {@code true} if the bit is enabled, {@code false} otherwise.
+ * @throws IndexOutOfBoundsException if bitIndex specifies a bit not in the range being tracked.
+ */
+ public static boolean contains(final int[] bitMaps, final int bitIndex) {
+ return (bitMaps[getIntIndex(bitIndex)] & getIntBit(bitIndex)) != 0;
Review Comment:
The Bitmap checks are performed on every ACL in the Trie during some operations. While it may make sense to add range checks on a general case library, this is that that. This is a specific case where we know the values of the indexes before we start and where we want to reduce the overhead as much as possible.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: jira-unsubscribe@kafka.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] KAFKA-17423 Trie implementation [kafka]
Posted by "Claudenw (via GitHub)" <gi...@apache.org>.
Claudenw commented on code in PR #17087:
URL: https://github.com/apache/kafka/pull/17087#discussion_r1749199096
##########
metadata/src/main/java/org/apache/kafka/metadata/authorizer/trie/package-info.java:
##########
@@ -0,0 +1,70 @@
+/*
Review Comment:
This file is used by the javadoc process to create package information. The name is hard coded into the javadoc tool.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: jira-unsubscribe@kafka.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] KAFKA-17423 Trie implementation [kafka]
Posted by "Claudenw (via GitHub)" <gi...@apache.org>.
Claudenw commented on code in PR #17087:
URL: https://github.com/apache/kafka/pull/17087#discussion_r1749198935
##########
metadata/src/main/java/org/apache/kafka/metadata/authorizer/bitmap/BitMaps.java:
##########
@@ -0,0 +1,159 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+
+package org.apache.kafka.metadata.authorizer.bitmap;
+
+
+/**
+ * Contains functions to convert {@code int} indices into Bitmap bit positions and visa versa.
+ *
+ * <p>The functions view an array of longs as a collection of bit maps each containing 64 bits. The bits are arranged
+ * in memory as a little-endian long value. </p>
+ *
+ * This code is based on the BitMaps code in Apache Commons Collections.
+ * @see <a href="https://commons.apache.org/proper//commons-collections/apidocs/org/apache/commons/collections4/bloomfilter/BitMaps.html">Apache Commons Collections Bitmaps</a>
+ */
+public class BitMaps {
+ /** A bit shift to apply to an integer to divided by 32 (2^5). */
+ private static final int DIVIDE_BY_32 = 5;
+
+ /**
+ * Checks if the specified index bit is enabled in the array of bit maps.
+ *
+ * If the bit specified by bitIndex is not in the bit map false is returned.
+ *
+ * @param bitMaps The array of bit maps.
+ * @param bitIndex the index of the bit to locate.
+ * @return {@code true} if the bit is enabled, {@code false} otherwise.
+ * @throws IndexOutOfBoundsException if bitIndex specifies a bit not in the range being tracked.
+ */
+ public static boolean contains(final int[] bitMaps, final int bitIndex) {
+ return (bitMaps[getIntIndex(bitIndex)] & getIntBit(bitIndex)) != 0;
+ }
+
+ /**
+ * Checks if the specified index bit is enabled in the array of bit maps.
+ *
+ * If the bit specified by bitIndex is not in the bit map false is returned.
+ *
+ * @param bitMap The int bit map.
+ * @param bitIndex the index of the bit to locate.
+ * @return {@code true} if the bit is enabled, {@code false} otherwise.
+ * @throws IndexOutOfBoundsException if bitIndex specifies a bit not in the range being tracked.
+ */
+ public static boolean contains(final int bitMap, final int bitIndex) {
+ return (bitMap & getIntBit(bitIndex)) != 0;
Review Comment:
The Bitmap checks are performed on every ACL in the Trie during some operations. While it may make sense to add range checks on a general case library, this is that that. This is a specific case where we know the values of the indexes before we start and where we want to reduce the overhead as much as possible.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: jira-unsubscribe@kafka.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] KAFKA-17423 Trie implementation [kafka]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #17087:
URL: https://github.com/apache/kafka/pull/17087#issuecomment-2832943831
This PR has been closed since it has not had any activity in 120 days. If you feel like this
was a mistake, or you would like to continue working on it, please feel free to re-open the
PR and ask for a review.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: jira-unsubscribe@kafka.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] KAFKA-17423 Trie implementation [kafka]
Posted by "chiacyu (via GitHub)" <gi...@apache.org>.
chiacyu commented on code in PR #17087:
URL: https://github.com/apache/kafka/pull/17087#discussion_r1749089551
##########
metadata/src/main/java/org/apache/kafka/metadata/authorizer/trie/Trie.java:
##########
@@ -0,0 +1,94 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.kafka.metadata.authorizer.trie;
+
+import java.util.function.BiFunction;
+import java.util.function.Function;
+
+/**
+ * The Trie is a Radix Trie structure indexed by strings.
+ * @param <T> the type of object held in the trie.
+ */
+public class Trie<T> {
+ /** the root node */
+ private Node<T> root;
+
+ /**
+ * Constructor.
+ * Creates an empty tree.
+ */
+ public Trie() {
+ clear();
Review Comment:
There's compilation error please check.
https://github.com/apache/kafka/actions/runs/10722721527/job/29734313780?pr=17087#step:6:2650
##########
metadata/src/main/java/org/apache/kafka/metadata/authorizer/bitmap/BitMaps.java:
##########
@@ -0,0 +1,159 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+
+package org.apache.kafka.metadata.authorizer.bitmap;
+
+
+/**
+ * Contains functions to convert {@code int} indices into Bitmap bit positions and visa versa.
+ *
+ * <p>The functions view an array of longs as a collection of bit maps each containing 64 bits. The bits are arranged
+ * in memory as a little-endian long value. </p>
+ *
+ * This code is based on the BitMaps code in Apache Commons Collections.
+ * @see <a href="https://commons.apache.org/proper//commons-collections/apidocs/org/apache/commons/collections4/bloomfilter/BitMaps.html">Apache Commons Collections Bitmaps</a>
+ */
+public class BitMaps {
+ /** A bit shift to apply to an integer to divided by 32 (2^5). */
+ private static final int DIVIDE_BY_32 = 5;
+
+ /**
+ * Checks if the specified index bit is enabled in the array of bit maps.
+ *
+ * If the bit specified by bitIndex is not in the bit map false is returned.
+ *
+ * @param bitMaps The array of bit maps.
+ * @param bitIndex the index of the bit to locate.
+ * @return {@code true} if the bit is enabled, {@code false} otherwise.
+ * @throws IndexOutOfBoundsException if bitIndex specifies a bit not in the range being tracked.
+ */
+ public static boolean contains(final int[] bitMaps, final int bitIndex) {
+ return (bitMaps[getIntIndex(bitIndex)] & getIntBit(bitIndex)) != 0;
Review Comment:
I think we can remove the `!= 0` but still remains the logic.
##########
metadata/src/main/java/org/apache/kafka/metadata/authorizer/bitmap/BitMaps.java:
##########
@@ -0,0 +1,159 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+
+package org.apache.kafka.metadata.authorizer.bitmap;
+
+
+/**
+ * Contains functions to convert {@code int} indices into Bitmap bit positions and visa versa.
+ *
+ * <p>The functions view an array of longs as a collection of bit maps each containing 64 bits. The bits are arranged
+ * in memory as a little-endian long value. </p>
+ *
+ * This code is based on the BitMaps code in Apache Commons Collections.
+ * @see <a href="https://commons.apache.org/proper//commons-collections/apidocs/org/apache/commons/collections4/bloomfilter/BitMaps.html">Apache Commons Collections Bitmaps</a>
+ */
+public class BitMaps {
+ /** A bit shift to apply to an integer to divided by 32 (2^5). */
+ private static final int DIVIDE_BY_32 = 5;
+
+ /**
+ * Checks if the specified index bit is enabled in the array of bit maps.
+ *
+ * If the bit specified by bitIndex is not in the bit map false is returned.
+ *
+ * @param bitMaps The array of bit maps.
+ * @param bitIndex the index of the bit to locate.
+ * @return {@code true} if the bit is enabled, {@code false} otherwise.
+ * @throws IndexOutOfBoundsException if bitIndex specifies a bit not in the range being tracked.
+ */
+ public static boolean contains(final int[] bitMaps, final int bitIndex) {
+ return (bitMaps[getIntIndex(bitIndex)] & getIntBit(bitIndex)) != 0;
+ }
+
+ /**
+ * Checks if the specified index bit is enabled in the array of bit maps.
+ *
+ * If the bit specified by bitIndex is not in the bit map false is returned.
+ *
+ * @param bitMap The int bit map.
+ * @param bitIndex the index of the bit to locate.
+ * @return {@code true} if the bit is enabled, {@code false} otherwise.
+ * @throws IndexOutOfBoundsException if bitIndex specifies a bit not in the range being tracked.
+ */
+ public static boolean contains(final int bitMap, final int bitIndex) {
+ return (bitMap & getIntBit(bitIndex)) != 0;
Review Comment:
Should check whether the index is out of range or not.
##########
metadata/src/main/java/org/apache/kafka/metadata/authorizer/bitmap/BitMaps.java:
##########
@@ -0,0 +1,159 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+
+package org.apache.kafka.metadata.authorizer.bitmap;
+
+
+/**
+ * Contains functions to convert {@code int} indices into Bitmap bit positions and visa versa.
+ *
+ * <p>The functions view an array of longs as a collection of bit maps each containing 64 bits. The bits are arranged
+ * in memory as a little-endian long value. </p>
+ *
+ * This code is based on the BitMaps code in Apache Commons Collections.
+ * @see <a href="https://commons.apache.org/proper//commons-collections/apidocs/org/apache/commons/collections4/bloomfilter/BitMaps.html">Apache Commons Collections Bitmaps</a>
+ */
+public class BitMaps {
+ /** A bit shift to apply to an integer to divided by 32 (2^5). */
+ private static final int DIVIDE_BY_32 = 5;
+
+ /**
+ * Checks if the specified index bit is enabled in the array of bit maps.
+ *
+ * If the bit specified by bitIndex is not in the bit map false is returned.
+ *
+ * @param bitMaps The array of bit maps.
+ * @param bitIndex the index of the bit to locate.
+ * @return {@code true} if the bit is enabled, {@code false} otherwise.
+ * @throws IndexOutOfBoundsException if bitIndex specifies a bit not in the range being tracked.
+ */
+ public static boolean contains(final int[] bitMaps, final int bitIndex) {
+ return (bitMaps[getIntIndex(bitIndex)] & getIntBit(bitIndex)) != 0;
+ }
+
+ /**
+ * Checks if the specified index bit is enabled in the array of bit maps.
+ *
+ * If the bit specified by bitIndex is not in the bit map false is returned.
+ *
+ * @param bitMap The int bit map.
+ * @param bitIndex the index of the bit to locate.
+ * @return {@code true} if the bit is enabled, {@code false} otherwise.
+ * @throws IndexOutOfBoundsException if bitIndex specifies a bit not in the range being tracked.
+ */
+ public static boolean contains(final int bitMap, final int bitIndex) {
+ return (bitMap & getIntBit(bitIndex)) != 0;
+ }
+
+ /**
+ * Gets the filter bit mask for the specified bit index assuming the filter is using 64-bit
+ * longs to store bits starting at index 0. The returned value is a {@code long} with only
+ * 1 bit set.
+ *
+ * <p>The index is assumed to be positive. For a positive index the result will match
+ * {@code 1L << (bitIndex % 64)}.</p>
+ *
+ * <p><em>If the input is negative the behavior is not defined.</em></p>
+ *
+ * @param bitIndex the bit index (assumed to be positive)
+ * @return the filter bit
+ */
+ public static int getIntBit(final int bitIndex) {
+ // Bit shifts only use the first 6 bits. Thus it is not necessary to mask this
+ // using 0x3f (63) or compute bitIndex % 64.
+ // Note: If the index is negative the shift will be (64 - (bitIndex & 0x3f)) and
+ // this will identify an incorrect bit.
+ return 1 << bitIndex;
+ }
+
+ /**
+ * Gets the filter index for the specified bit index assuming the filter is using 64-bit longs
+ * to store bits starting at index 0.
+ *
+ * <p>The index is assumed to be positive. For a positive index the result will match
+ * {@code bitIndex / 64}.</p>
+ *
+ * <p><em>The divide is performed using bit shifts. If the input is negative the behavior
+ * is not defined.</em></p>
+ *
+ * @param bitIndex the bit index (assumed to be positive)
+ * @return the index of the bit map in an array of bit maps.
+ */
+ public static int getIntIndex(final int bitIndex) {
+ // An integer divide by 32 is equivalent to a shift of 6 bits if the integer is
+ // positive.
+ // We do not explicitly check for a negative here. Instead we use a
+ // signed shift. Any negative index will produce a negative value
+ // by sign-extension and if used as an index into an array it will throw an
+ // exception.
+ return bitIndex >> DIVIDE_BY_32;
+ }
+
+ /**
+ * Performs a modulus calculation on an unsigned long and a positive integer divisor.
+ *
+ * <p>This method computes the same result as {@link Long#remainderUnsigned(long, long)}
+ * but assumes that the divisor is an integer in the range 1 to 2<sup>31</sup> - 1 inclusive,
+ * that is a strictly positive integer size.
+ *
+ * <p><em>If the divisor is negative the behavior is not defined.</em></p>
+ *
+ * @param dividend an unsigned long value to calculate the modulus of.
+ * @param divisor the divisor for the modulus calculation, must be strictly positive.
+ * @return the remainder or modulus value.
+ * @throws ArithmeticException if the divisor is zero
+ * @see Long#remainderUnsigned(long, long)
+ */
+ public static int mod(final long dividend, final int divisor) {
+ // See Hacker's Delight (2nd ed), section 9.3.
+ // Assume divisor is positive.
+ // Divide half the unsigned number and then double the quotient result.
+ final long quotient = (dividend >>> 1) / divisor << 1;
+ final long remainder = dividend - quotient * divisor;
+ // remainder in [0, 2 * divisor)
+ return (int) (remainder >= divisor ? remainder - divisor : remainder);
+ }
+
+ /**
+ * Calculates the number of bit maps (longs) required for the numberOfBits parameter.
+ *
+ * <p><em>If the input is negative the behavior is not defined.</em></p>
+ *
+ * @param numberOfBits the number of bits to store in the array of bit maps.
+ * @return the number of bit maps necessary.
+ */
+ public static int numberOfBitMaps(final int numberOfBits) {
Review Comment:
Should we add some conditional check to avoid `numberOfBits` is a negative value?
##########
metadata/src/main/java/org/apache/kafka/metadata/authorizer/bitmap/BitMaps.java:
##########
@@ -0,0 +1,159 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+
+package org.apache.kafka.metadata.authorizer.bitmap;
+
+
+/**
+ * Contains functions to convert {@code int} indices into Bitmap bit positions and visa versa.
+ *
+ * <p>The functions view an array of longs as a collection of bit maps each containing 64 bits. The bits are arranged
+ * in memory as a little-endian long value. </p>
+ *
+ * This code is based on the BitMaps code in Apache Commons Collections.
+ * @see <a href="https://commons.apache.org/proper//commons-collections/apidocs/org/apache/commons/collections4/bloomfilter/BitMaps.html">Apache Commons Collections Bitmaps</a>
+ */
+public class BitMaps {
+ /** A bit shift to apply to an integer to divided by 32 (2^5). */
+ private static final int DIVIDE_BY_32 = 5;
+
+ /**
+ * Checks if the specified index bit is enabled in the array of bit maps.
+ *
+ * If the bit specified by bitIndex is not in the bit map false is returned.
+ *
+ * @param bitMaps The array of bit maps.
+ * @param bitIndex the index of the bit to locate.
+ * @return {@code true} if the bit is enabled, {@code false} otherwise.
+ * @throws IndexOutOfBoundsException if bitIndex specifies a bit not in the range being tracked.
+ */
+ public static boolean contains(final int[] bitMaps, final int bitIndex) {
+ return (bitMaps[getIntIndex(bitIndex)] & getIntBit(bitIndex)) != 0;
Review Comment:
Should check whether the index is out of range or not.
##########
metadata/src/main/java/org/apache/kafka/metadata/authorizer/trie/package-info.java:
##########
@@ -0,0 +1,70 @@
+/*
Review Comment:
Maybe change the filename to `PackageInfo.java` and also what's the purpose of this file?
##########
metadata/src/main/java/org/apache/kafka/metadata/authorizer/bitmap/BitMaps.java:
##########
@@ -0,0 +1,159 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+
+package org.apache.kafka.metadata.authorizer.bitmap;
+
+
+/**
+ * Contains functions to convert {@code int} indices into Bitmap bit positions and visa versa.
+ *
+ * <p>The functions view an array of longs as a collection of bit maps each containing 64 bits. The bits are arranged
+ * in memory as a little-endian long value. </p>
+ *
+ * This code is based on the BitMaps code in Apache Commons Collections.
+ * @see <a href="https://commons.apache.org/proper//commons-collections/apidocs/org/apache/commons/collections4/bloomfilter/BitMaps.html">Apache Commons Collections Bitmaps</a>
+ */
+public class BitMaps {
+ /** A bit shift to apply to an integer to divided by 32 (2^5). */
+ private static final int DIVIDE_BY_32 = 5;
+
+ /**
+ * Checks if the specified index bit is enabled in the array of bit maps.
+ *
+ * If the bit specified by bitIndex is not in the bit map false is returned.
+ *
+ * @param bitMaps The array of bit maps.
+ * @param bitIndex the index of the bit to locate.
+ * @return {@code true} if the bit is enabled, {@code false} otherwise.
+ * @throws IndexOutOfBoundsException if bitIndex specifies a bit not in the range being tracked.
+ */
+ public static boolean contains(final int[] bitMaps, final int bitIndex) {
+ return (bitMaps[getIntIndex(bitIndex)] & getIntBit(bitIndex)) != 0;
+ }
+
+ /**
+ * Checks if the specified index bit is enabled in the array of bit maps.
+ *
+ * If the bit specified by bitIndex is not in the bit map false is returned.
+ *
+ * @param bitMap The int bit map.
+ * @param bitIndex the index of the bit to locate.
+ * @return {@code true} if the bit is enabled, {@code false} otherwise.
+ * @throws IndexOutOfBoundsException if bitIndex specifies a bit not in the range being tracked.
+ */
+ public static boolean contains(final int bitMap, final int bitIndex) {
+ return (bitMap & getIntBit(bitIndex)) != 0;
+ }
+
+ /**
+ * Gets the filter bit mask for the specified bit index assuming the filter is using 64-bit
+ * longs to store bits starting at index 0. The returned value is a {@code long} with only
+ * 1 bit set.
+ *
+ * <p>The index is assumed to be positive. For a positive index the result will match
+ * {@code 1L << (bitIndex % 64)}.</p>
+ *
+ * <p><em>If the input is negative the behavior is not defined.</em></p>
+ *
+ * @param bitIndex the bit index (assumed to be positive)
+ * @return the filter bit
+ */
+ public static int getIntBit(final int bitIndex) {
+ // Bit shifts only use the first 6 bits. Thus it is not necessary to mask this
+ // using 0x3f (63) or compute bitIndex % 64.
+ // Note: If the index is negative the shift will be (64 - (bitIndex & 0x3f)) and
+ // this will identify an incorrect bit.
+ return 1 << bitIndex;
+ }
+
+ /**
+ * Gets the filter index for the specified bit index assuming the filter is using 64-bit longs
+ * to store bits starting at index 0.
+ *
+ * <p>The index is assumed to be positive. For a positive index the result will match
+ * {@code bitIndex / 64}.</p>
+ *
+ * <p><em>The divide is performed using bit shifts. If the input is negative the behavior
+ * is not defined.</em></p>
+ *
+ * @param bitIndex the bit index (assumed to be positive)
+ * @return the index of the bit map in an array of bit maps.
+ */
+ public static int getIntIndex(final int bitIndex) {
+ // An integer divide by 32 is equivalent to a shift of 6 bits if the integer is
+ // positive.
+ // We do not explicitly check for a negative here. Instead we use a
+ // signed shift. Any negative index will produce a negative value
+ // by sign-extension and if used as an index into an array it will throw an
+ // exception.
+ return bitIndex >> DIVIDE_BY_32;
+ }
+
+ /**
+ * Performs a modulus calculation on an unsigned long and a positive integer divisor.
+ *
+ * <p>This method computes the same result as {@link Long#remainderUnsigned(long, long)}
+ * but assumes that the divisor is an integer in the range 1 to 2<sup>31</sup> - 1 inclusive,
+ * that is a strictly positive integer size.
+ *
+ * <p><em>If the divisor is negative the behavior is not defined.</em></p>
+ *
+ * @param dividend an unsigned long value to calculate the modulus of.
+ * @param divisor the divisor for the modulus calculation, must be strictly positive.
+ * @return the remainder or modulus value.
+ * @throws ArithmeticException if the divisor is zero
+ * @see Long#remainderUnsigned(long, long)
+ */
+ public static int mod(final long dividend, final int divisor) {
+ // See Hacker's Delight (2nd ed), section 9.3.
+ // Assume divisor is positive.
+ // Divide half the unsigned number and then double the quotient result.
+ final long quotient = (dividend >>> 1) / divisor << 1;
+ final long remainder = dividend - quotient * divisor;
+ // remainder in [0, 2 * divisor)
+ return (int) (remainder >= divisor ? remainder - divisor : remainder);
+ }
+
+ /**
+ * Calculates the number of bit maps (longs) required for the numberOfBits parameter.
+ *
+ * <p><em>If the input is negative the behavior is not defined.</em></p>
+ *
+ * @param numberOfBits the number of bits to store in the array of bit maps.
+ * @return the number of bit maps necessary.
+ */
+ public static int numberOfBitMaps(final int numberOfBits) {
+ return (numberOfBits - 1 >> DIVIDE_BY_32) + 1;
+ }
+
+ /**
+ * Sets the bit in the bit maps.
+ * <p><em>Does not perform range checking</em></p>
+ *
+ * @param bitMaps The array of bit maps.
+ * @param bitIndex the index of the bit to set.
+ * @throws IndexOutOfBoundsException if bitIndex specifies a bit not in the range being tracked.
+ */
+ public static void set(final int[] bitMaps, final int bitIndex) {
+ bitMaps[getIntIndex(bitIndex)] |= getIntBit(bitIndex);
Review Comment:
Should check whether the index is out of range or not.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: jira-unsubscribe@kafka.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] KAFKA-17423 Trie implementation [kafka]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #17087:
URL: https://github.com/apache/kafka/pull/17087#issuecomment-2760101352
This PR is being marked as stale since it has not had any activity in 90 days. If you
would like to keep this PR alive, please leave a comment asking for a review. If the PR has
merge conflicts, update it with the latest from the base branch.
<p>
If you are having difficulty finding a reviewer, please reach out on the
[mailing list](https://kafka.apache.org/contact).
<p>
If this PR is no longer valid or desired, please feel free to close it. If no activity
occurs in the next 30 days, it will be automatically closed.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: jira-unsubscribe@kafka.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] KAFKA-17423 Trie implementation [kafka]
Posted by "Claudenw (via GitHub)" <gi...@apache.org>.
Claudenw commented on code in PR #17087:
URL: https://github.com/apache/kafka/pull/17087#discussion_r1749198889
##########
metadata/src/main/java/org/apache/kafka/metadata/authorizer/bitmap/BitMaps.java:
##########
@@ -0,0 +1,159 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+
+package org.apache.kafka.metadata.authorizer.bitmap;
+
+
+/**
+ * Contains functions to convert {@code int} indices into Bitmap bit positions and visa versa.
+ *
+ * <p>The functions view an array of longs as a collection of bit maps each containing 64 bits. The bits are arranged
+ * in memory as a little-endian long value. </p>
+ *
+ * This code is based on the BitMaps code in Apache Commons Collections.
+ * @see <a href="https://commons.apache.org/proper//commons-collections/apidocs/org/apache/commons/collections4/bloomfilter/BitMaps.html">Apache Commons Collections Bitmaps</a>
+ */
+public class BitMaps {
+ /** A bit shift to apply to an integer to divided by 32 (2^5). */
+ private static final int DIVIDE_BY_32 = 5;
+
+ /**
+ * Checks if the specified index bit is enabled in the array of bit maps.
+ *
+ * If the bit specified by bitIndex is not in the bit map false is returned.
+ *
+ * @param bitMaps The array of bit maps.
+ * @param bitIndex the index of the bit to locate.
+ * @return {@code true} if the bit is enabled, {@code false} otherwise.
+ * @throws IndexOutOfBoundsException if bitIndex specifies a bit not in the range being tracked.
+ */
+ public static boolean contains(final int[] bitMaps, final int bitIndex) {
+ return (bitMaps[getIntIndex(bitIndex)] & getIntBit(bitIndex)) != 0;
+ }
+
+ /**
+ * Checks if the specified index bit is enabled in the array of bit maps.
+ *
+ * If the bit specified by bitIndex is not in the bit map false is returned.
+ *
+ * @param bitMap The int bit map.
+ * @param bitIndex the index of the bit to locate.
+ * @return {@code true} if the bit is enabled, {@code false} otherwise.
+ * @throws IndexOutOfBoundsException if bitIndex specifies a bit not in the range being tracked.
+ */
+ public static boolean contains(final int bitMap, final int bitIndex) {
+ return (bitMap & getIntBit(bitIndex)) != 0;
+ }
+
+ /**
+ * Gets the filter bit mask for the specified bit index assuming the filter is using 64-bit
+ * longs to store bits starting at index 0. The returned value is a {@code long} with only
+ * 1 bit set.
+ *
+ * <p>The index is assumed to be positive. For a positive index the result will match
+ * {@code 1L << (bitIndex % 64)}.</p>
+ *
+ * <p><em>If the input is negative the behavior is not defined.</em></p>
+ *
+ * @param bitIndex the bit index (assumed to be positive)
+ * @return the filter bit
+ */
+ public static int getIntBit(final int bitIndex) {
+ // Bit shifts only use the first 6 bits. Thus it is not necessary to mask this
+ // using 0x3f (63) or compute bitIndex % 64.
+ // Note: If the index is negative the shift will be (64 - (bitIndex & 0x3f)) and
+ // this will identify an incorrect bit.
+ return 1 << bitIndex;
+ }
+
+ /**
+ * Gets the filter index for the specified bit index assuming the filter is using 64-bit longs
+ * to store bits starting at index 0.
+ *
+ * <p>The index is assumed to be positive. For a positive index the result will match
+ * {@code bitIndex / 64}.</p>
+ *
+ * <p><em>The divide is performed using bit shifts. If the input is negative the behavior
+ * is not defined.</em></p>
+ *
+ * @param bitIndex the bit index (assumed to be positive)
+ * @return the index of the bit map in an array of bit maps.
+ */
+ public static int getIntIndex(final int bitIndex) {
+ // An integer divide by 32 is equivalent to a shift of 6 bits if the integer is
+ // positive.
+ // We do not explicitly check for a negative here. Instead we use a
+ // signed shift. Any negative index will produce a negative value
+ // by sign-extension and if used as an index into an array it will throw an
+ // exception.
+ return bitIndex >> DIVIDE_BY_32;
+ }
+
+ /**
+ * Performs a modulus calculation on an unsigned long and a positive integer divisor.
+ *
+ * <p>This method computes the same result as {@link Long#remainderUnsigned(long, long)}
+ * but assumes that the divisor is an integer in the range 1 to 2<sup>31</sup> - 1 inclusive,
+ * that is a strictly positive integer size.
+ *
+ * <p><em>If the divisor is negative the behavior is not defined.</em></p>
+ *
+ * @param dividend an unsigned long value to calculate the modulus of.
+ * @param divisor the divisor for the modulus calculation, must be strictly positive.
+ * @return the remainder or modulus value.
+ * @throws ArithmeticException if the divisor is zero
+ * @see Long#remainderUnsigned(long, long)
+ */
+ public static int mod(final long dividend, final int divisor) {
+ // See Hacker's Delight (2nd ed), section 9.3.
+ // Assume divisor is positive.
+ // Divide half the unsigned number and then double the quotient result.
+ final long quotient = (dividend >>> 1) / divisor << 1;
+ final long remainder = dividend - quotient * divisor;
+ // remainder in [0, 2 * divisor)
+ return (int) (remainder >= divisor ? remainder - divisor : remainder);
+ }
+
+ /**
+ * Calculates the number of bit maps (longs) required for the numberOfBits parameter.
+ *
+ * <p><em>If the input is negative the behavior is not defined.</em></p>
+ *
+ * @param numberOfBits the number of bits to store in the array of bit maps.
+ * @return the number of bit maps necessary.
+ */
+ public static int numberOfBitMaps(final int numberOfBits) {
Review Comment:
The Bitmap checks are performed on every ACL in the Trie during some operations. While it may make sense to add range checks on a general case library, this is that that. This is a specific case where we know the values of the indexes before we start and where we want to reduce the overhead as much as possible.
##########
metadata/src/main/java/org/apache/kafka/metadata/authorizer/bitmap/BitMaps.java:
##########
@@ -0,0 +1,159 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+
+package org.apache.kafka.metadata.authorizer.bitmap;
+
+
+/**
+ * Contains functions to convert {@code int} indices into Bitmap bit positions and visa versa.
+ *
+ * <p>The functions view an array of longs as a collection of bit maps each containing 64 bits. The bits are arranged
+ * in memory as a little-endian long value. </p>
+ *
+ * This code is based on the BitMaps code in Apache Commons Collections.
+ * @see <a href="https://commons.apache.org/proper//commons-collections/apidocs/org/apache/commons/collections4/bloomfilter/BitMaps.html">Apache Commons Collections Bitmaps</a>
+ */
+public class BitMaps {
+ /** A bit shift to apply to an integer to divided by 32 (2^5). */
+ private static final int DIVIDE_BY_32 = 5;
+
+ /**
+ * Checks if the specified index bit is enabled in the array of bit maps.
+ *
+ * If the bit specified by bitIndex is not in the bit map false is returned.
+ *
+ * @param bitMaps The array of bit maps.
+ * @param bitIndex the index of the bit to locate.
+ * @return {@code true} if the bit is enabled, {@code false} otherwise.
+ * @throws IndexOutOfBoundsException if bitIndex specifies a bit not in the range being tracked.
+ */
+ public static boolean contains(final int[] bitMaps, final int bitIndex) {
+ return (bitMaps[getIntIndex(bitIndex)] & getIntBit(bitIndex)) != 0;
+ }
+
+ /**
+ * Checks if the specified index bit is enabled in the array of bit maps.
+ *
+ * If the bit specified by bitIndex is not in the bit map false is returned.
+ *
+ * @param bitMap The int bit map.
+ * @param bitIndex the index of the bit to locate.
+ * @return {@code true} if the bit is enabled, {@code false} otherwise.
+ * @throws IndexOutOfBoundsException if bitIndex specifies a bit not in the range being tracked.
+ */
+ public static boolean contains(final int bitMap, final int bitIndex) {
+ return (bitMap & getIntBit(bitIndex)) != 0;
+ }
+
+ /**
+ * Gets the filter bit mask for the specified bit index assuming the filter is using 64-bit
+ * longs to store bits starting at index 0. The returned value is a {@code long} with only
+ * 1 bit set.
+ *
+ * <p>The index is assumed to be positive. For a positive index the result will match
+ * {@code 1L << (bitIndex % 64)}.</p>
+ *
+ * <p><em>If the input is negative the behavior is not defined.</em></p>
+ *
+ * @param bitIndex the bit index (assumed to be positive)
+ * @return the filter bit
+ */
+ public static int getIntBit(final int bitIndex) {
+ // Bit shifts only use the first 6 bits. Thus it is not necessary to mask this
+ // using 0x3f (63) or compute bitIndex % 64.
+ // Note: If the index is negative the shift will be (64 - (bitIndex & 0x3f)) and
+ // this will identify an incorrect bit.
+ return 1 << bitIndex;
+ }
+
+ /**
+ * Gets the filter index for the specified bit index assuming the filter is using 64-bit longs
+ * to store bits starting at index 0.
+ *
+ * <p>The index is assumed to be positive. For a positive index the result will match
+ * {@code bitIndex / 64}.</p>
+ *
+ * <p><em>The divide is performed using bit shifts. If the input is negative the behavior
+ * is not defined.</em></p>
+ *
+ * @param bitIndex the bit index (assumed to be positive)
+ * @return the index of the bit map in an array of bit maps.
+ */
+ public static int getIntIndex(final int bitIndex) {
+ // An integer divide by 32 is equivalent to a shift of 6 bits if the integer is
+ // positive.
+ // We do not explicitly check for a negative here. Instead we use a
+ // signed shift. Any negative index will produce a negative value
+ // by sign-extension and if used as an index into an array it will throw an
+ // exception.
+ return bitIndex >> DIVIDE_BY_32;
+ }
+
+ /**
+ * Performs a modulus calculation on an unsigned long and a positive integer divisor.
+ *
+ * <p>This method computes the same result as {@link Long#remainderUnsigned(long, long)}
+ * but assumes that the divisor is an integer in the range 1 to 2<sup>31</sup> - 1 inclusive,
+ * that is a strictly positive integer size.
+ *
+ * <p><em>If the divisor is negative the behavior is not defined.</em></p>
+ *
+ * @param dividend an unsigned long value to calculate the modulus of.
+ * @param divisor the divisor for the modulus calculation, must be strictly positive.
+ * @return the remainder or modulus value.
+ * @throws ArithmeticException if the divisor is zero
+ * @see Long#remainderUnsigned(long, long)
+ */
+ public static int mod(final long dividend, final int divisor) {
+ // See Hacker's Delight (2nd ed), section 9.3.
+ // Assume divisor is positive.
+ // Divide half the unsigned number and then double the quotient result.
+ final long quotient = (dividend >>> 1) / divisor << 1;
+ final long remainder = dividend - quotient * divisor;
+ // remainder in [0, 2 * divisor)
+ return (int) (remainder >= divisor ? remainder - divisor : remainder);
+ }
+
+ /**
+ * Calculates the number of bit maps (longs) required for the numberOfBits parameter.
+ *
+ * <p><em>If the input is negative the behavior is not defined.</em></p>
+ *
+ * @param numberOfBits the number of bits to store in the array of bit maps.
+ * @return the number of bit maps necessary.
+ */
+ public static int numberOfBitMaps(final int numberOfBits) {
+ return (numberOfBits - 1 >> DIVIDE_BY_32) + 1;
+ }
+
+ /**
+ * Sets the bit in the bit maps.
+ * <p><em>Does not perform range checking</em></p>
+ *
+ * @param bitMaps The array of bit maps.
+ * @param bitIndex the index of the bit to set.
+ * @throws IndexOutOfBoundsException if bitIndex specifies a bit not in the range being tracked.
+ */
+ public static void set(final int[] bitMaps, final int bitIndex) {
+ bitMaps[getIntIndex(bitIndex)] |= getIntBit(bitIndex);
Review Comment:
The Bitmap checks are performed on every ACL in the Trie during some operations. While it may make sense to add range checks on a general case library, this is that that. This is a specific case where we know the values of the indexes before we start and where we want to reduce the overhead as much as possible.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: jira-unsubscribe@kafka.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] KAFKA-17423 Trie implementation [kafka]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] closed pull request #17087: KAFKA-17423 Trie implementation
URL: https://github.com/apache/kafka/pull/17087
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: jira-unsubscribe@kafka.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org