001/*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements.  See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership.  The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License.  You may obtain a copy of the License at
009 *
010 *     http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018package org.apache.hadoop.hbase.security.visibility;
019
020import java.io.IOException;
021import java.util.ArrayList;
022import java.util.HashMap;
023import java.util.List;
024import java.util.Map;
025import java.util.NavigableMap;
026import java.util.NavigableSet;
027import java.util.SortedMap;
028import java.util.SortedSet;
029import java.util.TreeMap;
030import java.util.TreeSet;
031import org.apache.hadoop.hbase.CellComparator;
032import org.apache.hadoop.hbase.ExtendedCell;
033import org.apache.hadoop.hbase.KeyValue;
034import org.apache.hadoop.hbase.Tag;
035import org.apache.hadoop.hbase.regionserver.querymatcher.NewVersionBehaviorTracker;
036import org.apache.yetus.audience.InterfaceAudience;
037import org.slf4j.Logger;
038import org.slf4j.LoggerFactory;
039
040/**
041 * Similar to MvccSensitiveTracker but tracks the visibility expression also before deciding if a
042 * Cell can be considered deleted
043 */
044@InterfaceAudience.Private
045public class VisibilityNewVersionBehaivorTracker extends NewVersionBehaviorTracker {
046  private static final Logger LOG =
047    LoggerFactory.getLogger(VisibilityNewVersionBehaivorTracker.class);
048
049  public VisibilityNewVersionBehaivorTracker(NavigableSet<byte[]> columns,
050    CellComparator cellComparator, int minVersion, int maxVersion, int resultMaxVersions,
051    long oldestUnexpiredTS) {
052    super(columns, cellComparator, minVersion, maxVersion, resultMaxVersions, oldestUnexpiredTS);
053  }
054
055  private static class TagInfo {
056    List<Tag> tags;
057    Byte format;
058
059    private TagInfo(ExtendedCell c) {
060      tags = new ArrayList<>();
061      format = VisibilityUtils.extractVisibilityTags(c, tags);
062    }
063
064    private TagInfo() {
065      tags = new ArrayList<>();
066    }
067  }
068
069  private class VisibilityDeleteVersionsNode extends DeleteVersionsNode {
070    private TagInfo tagInfo;
071
072    // <timestamp, set<mvcc>>
073    // Key is ts of version deletes, value is its mvccs.
074    // We may delete more than one time for a version.
075    private Map<Long, SortedMap<Long, TagInfo>> deletesMap = new HashMap<>();
076
077    // <mvcc, set<mvcc>>
078    // Key is mvcc of version deletes, value is mvcc of visible puts before the delete effect.
079    private NavigableMap<Long, SortedSet<Long>> mvccCountingMap = new TreeMap<>();
080
081    protected VisibilityDeleteVersionsNode(long ts, long mvcc, TagInfo tagInfo) {
082      this.tagInfo = tagInfo;
083      this.ts = ts;
084      this.mvcc = mvcc;
085      mvccCountingMap.put(Long.MAX_VALUE, new TreeSet<Long>());
086    }
087
088    @Override
089    protected VisibilityDeleteVersionsNode getDeepCopy() {
090      VisibilityDeleteVersionsNode node = new VisibilityDeleteVersionsNode(ts, mvcc, tagInfo);
091      for (Map.Entry<Long, SortedMap<Long, TagInfo>> e : deletesMap.entrySet()) {
092        node.deletesMap.put(e.getKey(), new TreeMap<>(e.getValue()));
093      }
094      for (Map.Entry<Long, SortedSet<Long>> e : mvccCountingMap.entrySet()) {
095        node.mvccCountingMap.put(e.getKey(), new TreeSet<>(e.getValue()));
096      }
097      return node;
098    }
099
100    @Override
101    public void addVersionDelete(ExtendedCell cell) {
102      SortedMap<Long, TagInfo> set = deletesMap.get(cell.getTimestamp());
103      if (set == null) {
104        set = new TreeMap<>();
105        deletesMap.put(cell.getTimestamp(), set);
106      }
107      set.put(cell.getSequenceId(), new TagInfo(cell));
108      // The init set should be the puts whose mvcc is smaller than this Delete. Because
109      // there may be some Puts masked by them. The Puts whose mvcc is larger than this Delete can
110      // not be copied to this node because we may delete one version and the oldest put may not be
111      // masked.
112      SortedSet<Long> nextValue = mvccCountingMap.ceilingEntry(cell.getSequenceId()).getValue();
113      SortedSet<Long> thisValue = new TreeSet<>(nextValue.headSet(cell.getSequenceId()));
114      mvccCountingMap.put(cell.getSequenceId(), thisValue);
115    }
116
117  }
118
119  @Override
120  public void add(ExtendedCell cell) {
121    prepare(cell);
122    byte type = cell.getTypeByte();
123    switch (KeyValue.Type.codeToType(type)) {
124      // By the order of seen. We put null cq at first.
125      case DeleteFamily: // Delete all versions of all columns of the specified family
126        delFamMap.put(cell.getSequenceId(), new VisibilityDeleteVersionsNode(cell.getTimestamp(),
127          cell.getSequenceId(), new TagInfo(cell)));
128        break;
129      case DeleteFamilyVersion: // Delete all columns of the specified family and specified version
130        delFamMap.ceilingEntry(cell.getSequenceId()).getValue().addVersionDelete(cell);
131        break;
132
133      // These two kinds of markers are mix with Puts.
134      case DeleteColumn: // Delete all versions of the specified column
135        delColMap.put(cell.getSequenceId(), new VisibilityDeleteVersionsNode(cell.getTimestamp(),
136          cell.getSequenceId(), new TagInfo(cell)));
137        break;
138      case Delete: // Delete the specified version of the specified column.
139        delColMap.ceilingEntry(cell.getSequenceId()).getValue().addVersionDelete(cell);
140        break;
141      default:
142        throw new AssertionError("Unknown delete marker type for " + cell);
143    }
144  }
145
146  private boolean tagMatched(ExtendedCell put, TagInfo delInfo) throws IOException {
147    List<Tag> putVisTags = new ArrayList<>();
148    Byte putCellVisTagsFormat = VisibilityUtils.extractVisibilityTags(put, putVisTags);
149    return putVisTags.isEmpty() == delInfo.tags.isEmpty()
150      && ((putVisTags.isEmpty() && delInfo.tags.isEmpty())
151        || VisibilityLabelServiceManager.getInstance().getVisibilityLabelService()
152          .matchVisibility(putVisTags, putCellVisTagsFormat, delInfo.tags, delInfo.format));
153  }
154
155  @Override
156  public DeleteResult isDeleted(ExtendedCell cell) {
157    try {
158      long duplicateMvcc = prepare(cell);
159
160      for (Map.Entry<Long, DeleteVersionsNode> e : delColMap.tailMap(cell.getSequenceId())
161        .entrySet()) {
162        VisibilityDeleteVersionsNode node = (VisibilityDeleteVersionsNode) e.getValue();
163        long deleteMvcc = Long.MAX_VALUE;
164        SortedMap<Long, TagInfo> deleteVersionMvccs = node.deletesMap.get(cell.getTimestamp());
165        if (deleteVersionMvccs != null) {
166          SortedMap<Long, TagInfo> tail = deleteVersionMvccs.tailMap(cell.getSequenceId());
167          for (Map.Entry<Long, TagInfo> entry : tail.entrySet()) {
168            if (tagMatched(cell, entry.getValue())) {
169              deleteMvcc = tail.firstKey();
170              break;
171            }
172          }
173        }
174        SortedMap<Long, SortedSet<Long>> subMap = node.mvccCountingMap.subMap(cell.getSequenceId(),
175          true, Math.min(duplicateMvcc, deleteMvcc), true);
176        for (Map.Entry<Long, SortedSet<Long>> seg : subMap.entrySet()) {
177          if (seg.getValue().size() >= maxVersions) {
178            return DeleteResult.VERSION_MASKED;
179          }
180          seg.getValue().add(cell.getSequenceId());
181        }
182        if (deleteMvcc < Long.MAX_VALUE) {
183          return DeleteResult.VERSION_DELETED;
184        }
185
186        if (cell.getTimestamp() <= node.ts && tagMatched(cell, node.tagInfo)) {
187          return DeleteResult.COLUMN_DELETED;
188        }
189      }
190      if (duplicateMvcc < Long.MAX_VALUE) {
191        return DeleteResult.VERSION_MASKED;
192      }
193    } catch (IOException e) {
194      LOG.error("Error in isDeleted() check! Will treat cell as not deleted", e);
195    }
196    return DeleteResult.NOT_DELETED;
197  }
198
199  @Override
200  protected void resetInternal() {
201    delFamMap.put(Long.MAX_VALUE,
202      new VisibilityDeleteVersionsNode(Long.MIN_VALUE, Long.MAX_VALUE, new TagInfo()));
203  }
204}