wordpress 恶意访问

wordpress 恶意访问

在vps上抓包分析telegram协议时,意外发现有人尝试登录我的wordpress后台,很是意外,看来安全意识不能没有啊。

然后我装了个wordpress插件simple login log来记录登录日志,实验发现并不能记录登录失败的日志,所以看了下simple login log插件源码,simple-login-log.php文件中有以下代码行,

if( isset($this->opt['failed_attempts']) )

因为对php语言不是很了解,也没太仔细看opt在哪初始化或者修改的,索性直接把以上代码全替换成

if( 1 )

估计simple login log作者这么做是怕有攻击者对你网站实施密码爆破,使得mysql数据库爆掉。

而后就能看到登录失败的日志了。

仔细观察一下时间,你会发现这些人还蛮专业,隔两个小时尝试一次,怕短时间内多次访问被禁掉。

有一些插件可以做一些防护,比如:WP Limit Login Attempts、WP-Ban等,但考虑到本来vps内存cpu呀就不够用的,我就没安装这些插件了黑客还是蛮多的,不过我这小站也没啥,任他们去吧

 

Android QQ/微信 数据库

Android QQ/微信 数据库

QQ和微信数据本地数据库,可以获取聊天信息以及好友信息等。

QQ

安卓手机QQ数据库:/data/data/com.tencent.qq/databases/QQ号.db(手机root后可获取 RE浏览器);
数据库文件为sqlite数据库;
私聊天记录放在表:mr_friend_MD5(QQ号)_New
群聊天记录放在表:mr_troop_MD5(群号)_New

sqlcipher.exe打开数据库发现一些信息乱码,经过加密。加密方法循环异或IMEI号。

解密demo:

# -*- coding: utf-8 -*-
import sqlite3

IMEI="866536022175869"
conn = sqlite3.connect("971774262.db")
cursor = conn.execute("SELECT frienduin,selfuin,senderuin,msgdata  from mr_troop_158C59D128304F55302B275E6427CA1E_New ")
print "select database successfully";
print "群号\t\t己方QQ\t\t发送方QQ\t\t聊天内容"
for row in cursor:
    a= row[0]
    #print a
    sbstr=""
    for i in range(0,len(a)):
        sbstr+=chr(ord(a[i])^ord(IMEI[i%15]))
    sbstr+="\t"
    a= row[1]
    for i in range(0,len(a)):
        sbstr+=chr(ord(a[i])^ord(IMEI[i%15]))
    sbstr+="\t"
    a= row[2]
    for i in range(0,len(a)):
        sbstr+=chr(ord(a[i])^ord(IMEI[i%15]))
    sbstr+="\t"
    a= row[3]
    for i in range(0,len(a)):
        sbstr+=chr(ord(a[i])^ord(IMEI[i%15]))
    print sbstr

微信

安卓微信数据库:/data/data/com.tencent.mm/MicroMsg    EnMicroMsg.db (需要ROOT)

数据库整个加密,可以用sqlcipher.exe软件直接打开,也可以自己写代码。

数据库密码:拼接IMEI和uin,通过md5加密后,取前7位小写的字符串

uin获取:/data/data/com.tencent.mm/shared_prefs/auth_info_key_prefs.xml (需要ROOT)

leveldb log读写

leveldb log读写

leveldb在内存存储为Memtable,为防止异常情况Memtable没来得及写入SSTable文件程序挂掉,leveldb首先会写记录进入log文件,再把记录写入Memtable。这样即使异常挂掉也可以从log文件恢复数据。

log相关的代码在

  • db/log_format.h
  • db/log_reader.h
  • db/log_reader.cc
  • db/log_writer.h
  • db/log_writer.cc

1.log文件格式

log_format.h头文件

#ifndef STORAGE_LEVELDB_DB_LOG_FORMAT_H_
#define STORAGE_LEVELDB_DB_LOG_FORMAT_H_

namespace leveldb {
namespace log {

enum RecordType {
  // Zero is reserved for preallocated files
  kZeroType = 0,

  kFullType = 1,

  // For fragments
  kFirstType = 2,
  kMiddleType = 3,
  kLastType = 4
};
static const int kMaxRecordType = kLastType;

static const int kBlockSize = 32768; //32K

// Header is checksum (4 bytes), length (2 bytes), type (1 byte).
static const int kHeaderSize = 4 + 2 + 1;

}  // namespace log
}  // namespace leveldb

#endif  // STORAGE_LEVELDB_DB_LOG_FORMAT_H_

从这头文件可以看出,log文件分块,每一块32768字节(32K),当一条记录过大在1个block装不下时,记录可以分几部分装在不同的block里,每一部分有一个7字节的头(4字节crc校验码+2字节数据长度+1字节type)。

 

为什么拿2字节来表示长度?因为每部分数据不可能超过32K( 2^16 > 32K > 2^8 ),两个字节足够了。

 

下图copy from web

 

2.log的写入逻辑

Status Writer::AddRecord(const Slice& slice) {
  const char* ptr = slice.data();
  size_t left = slice.size();

  // Fragment the record if necessary and emit it.  Note that if slice
  // is empty, we still want to iterate once to emit a single
  // zero-length record
  Status s;
  bool begin = true;
  do {
    const int leftover = kBlockSize - block_offset_;
    assert(leftover >= 0);
    if (leftover < kHeaderSize) {
      // Switch to a new block
      if (leftover > 0) {
        // Fill the trailer (literal below relies on kHeaderSize being 7)
        //当块剩余字节连头都装不下时填充0
        assert(kHeaderSize == 7);
        dest_->Append(Slice("\x00\x00\x00\x00\x00\x00", leftover));
      }
      block_offset_ = 0;
    }

    // Invariant: we never leave < kHeaderSize bytes in a block.
    assert(kBlockSize - block_offset_ - kHeaderSize >= 0);

	//根据标志、长度确定类型:
	//kFullType(整条记录都在可以放到本block),
	//kFirstType(第一部分放到本block)	,kMiddleType...kLastType..
    const size_t avail = kBlockSize - block_offset_ - kHeaderSize;
    const size_t fragment_length = (left < avail) ? left : avail;

    RecordType type;
    const bool end = (left == fragment_length);
    if (begin && end) {
      type = kFullType;
    } else if (begin) {
      type = kFirstType;
    } else if (end) {
      type = kLastType;
    } else {
      type = kMiddleType;
    }

    s = EmitPhysicalRecord(type, ptr, fragment_length);
    ptr += fragment_length;
    left -= fragment_length;
    begin = false;
  } while (s.ok() && left > 0);
  return s;
}

Status Writer::EmitPhysicalRecord(RecordType t, const char* ptr, size_t n) {
  assert(n <= 0xffff);  // Must fit in two bytes
  assert(block_offset_ + kHeaderSize + n <= kBlockSize);

  // Format the header
  char buf[kHeaderSize];
  buf[4] = static_cast<char>(n & 0xff);
  buf[5] = static_cast<char>(n >> 8);
  buf[6] = static_cast<char>(t);

  // Compute the crc of the record type and the payload.
  uint32_t crc = crc32c::Extend(type_crc_[t], ptr, n);
  crc = crc32c::Mask(crc);                 // Adjust for storage
  EncodeFixed32(buf, crc);

  // Write the header and the payload
  Status s = dest_->Append(Slice(buf, kHeaderSize));
  if (s.ok()) {
    s = dest_->Append(Slice(ptr, n));
    if (s.ok()) {
      s = dest_->Flush();
    }
  }
  block_offset_ += kHeaderSize + n;
  return s;
}

循环计算长度、打上Type标签、计算CRC,然后Append到buffer中,再然后Flush到文件中(flush到文件中并不准确,暂且这么一说吧,为什么?见第4小结)。

3.基于POSIX的WritableFile接口实现

env.h是为跨平台准备的env接口,在这里我们只看其posix实现(env_posix.cc)

class PosixWritableFile : public WritableFile {
 private:
  // buf_[0, pos_-1] contains data to be written to fd_.
  std::string filename_;
  int fd_;
  char buf_[kBufSize];
  size_t pos_;

 public:
  PosixWritableFile(const std::string& fname, int fd)
      : filename_(fname), fd_(fd), pos_(0) { }

  ~PosixWritableFile() {
    if (fd_ >= 0) {
      // Ignoring any potential errors
      Close();
    }
  }

  virtual Status Append(const Slice& data) {
    size_t n = data.size();
    const char* p = data.data();

    // Fit as much as possible into buffer.
    size_t copy = std::min(n, kBufSize - pos_);
    memcpy(buf_ + pos_, p, copy);
    p += copy;
    n -= copy;
    pos_ += copy;
    if (n == 0) {
      return Status::OK();
    }

    // Can't fit in buffer, so need to do at least one write.
    Status s = FlushBuffered();
    if (!s.ok()) {
      return s;
    }

    // Small writes go to buffer, large writes are written directly.
    if (n < kBufSize) {
      memcpy(buf_, p, n);
      pos_ = n;
      return Status::OK();
    }
    return WriteRaw(p, n);
  }

  virtual Status Close() {
    Status result = FlushBuffered();
    const int r = close(fd_);
    if (r < 0 && result.ok()) {
      result = PosixError(filename_, errno);
    }
    fd_ = -1;
    return result;
  }

  virtual Status Flush() {
    return FlushBuffered();
  }

  Status SyncDirIfManifest() {
    const char* f = filename_.c_str();
    const char* sep = strrchr(f, '/');
    Slice basename;
    std::string dir;
    if (sep == nullptr) {
      dir = ".";
      basename = f;
    } else {
      dir = std::string(f, sep - f);
      basename = sep + 1;
    }
    Status s;
    if (basename.starts_with("MANIFEST")) {
      int fd = open(dir.c_str(), O_RDONLY);
      if (fd < 0) {
        s = PosixError(dir, errno);
      } else {
        if (fsync(fd) < 0) {
          s = PosixError(dir, errno);
        }
        close(fd);
      }
    }
    return s;
  }

  virtual Status Sync() {
    // Ensure new files referred to by the manifest are in the filesystem.
    Status s = SyncDirIfManifest();
    if (!s.ok()) {
      return s;
    }
    s = FlushBuffered();
    if (s.ok()) {
      if (fdatasync(fd_) != 0) {
        s = PosixError(filename_, errno);
      }
    }
    return s;
  }

 private:
  Status FlushBuffered() {
    Status s = WriteRaw(buf_, pos_);
    pos_ = 0;
    return s;
  }

  Status WriteRaw(const char* p, size_t n) {
    while (n > 0) {
      ssize_t r = write(fd_, p, n);
      if (r < 0) {
        if (errno == EINTR) {
          continue;  // Retry
        }
        return PosixError(filename_, errno);
      }
      p += r;
      n -= r;
    }
    return Status::OK();
  }
};

4.值得注意的fsync或fdatasync

在上一小结中有这么一个函数

// HAVE_FDATASYNC is defined in the auto-generated port_config.h, which is
// included by port_stdcxx.h.
#if !HAVE_FDATASYNC
#define fdatasync fsync
#endif  // !HAVE_FDATASYNC

  virtual Status Sync() {
    // Ensure new files referred to by the manifest are in the filesystem.
    Status s = SyncDirIfManifest();
    if (!s.ok()) {
      return s;
    }
    s = FlushBuffered();
    if (s.ok()) {
      if (fdatasync(fd_) != 0) {
        s = PosixError(filename_, errno);
      }
    }
    return s;
  }

若果你熟悉标准C的fopen、fprintf,会知道fprintf是有缓冲区的,刷新这些缓冲区的方法是fflush,确保信息传递到OS,但并不意味着它在磁盘上,它也可以在OS中缓冲。这里的write虽然是系统调用,write后的数据有可能在OS中缓冲,fsync或者fdatasync 会确保OS缓冲区中的内容写入物理磁盘。

你也许会在其他日志记录库中看到此类操作:

fprintf (myFileHandle, "something\n");  // output it
fflush (myFileHandle);                  // flush to OS
fsync (fileno (myFileHandle));          // flush to disk

fileno是一个函数,可以得到FILE*文件句柄的基础文件描述符,fsync在描述符上执行确保数据刷到磁盘。

fsync是相对昂贵的操作,因为磁盘写入通常比内存写入慢得多。

可以看一下leveldb的注释

// Options that control write operations
struct LEVELDB_EXPORT WriteOptions {
  // If true, the write will be flushed from the operating system
  // buffer cache (by calling WritableFile::Sync()) before the write
  // is considered complete.  If this flag is true, writes will be
  // slower.
  //
  // If this flag is false, and the machine crashes, some recent
  // writes may be lost.  Note that if it is just the process that
  // crashes (i.e., the machine does not reboot), no writes will be
  // lost even if sync==false.
  //
  // In other words, a DB write with sync==false has similar
  // crash semantics as the "write()" system call.  A DB write
  // with sync==true has similar crash semantics to a "write()"
  // system call followed by "fsync()".
  //
  // Default: false
  bool sync;

  WriteOptions()
      : sync(false) {
  }
};

默认情况下,sync的flag为false,后果是有可能会在异常的时候丢失一部分数据;如果为true的话write的时候会变慢。

参考:
https://stackoverflow.com/questions/10371017/fsync-vs-write-system-call
linux 同步IO: sync、fsync与fdatasync

5.log的读取逻辑

bool Reader::ReadRecord(Slice* record, std::string* scratch) {
  if (last_record_offset_ < initial_offset_) {
    if (!SkipToInitialBlock()) {
      return false;
    }
  }

  scratch->clear();
  record->clear();
  bool in_fragmented_record = false;
  // Record offset of the logical record that we're reading
  // 0 is a dummy value to make compilers happy
  uint64_t prospective_record_offset = 0;

  Slice fragment;
  while (true) {
    const unsigned int record_type = ReadPhysicalRecord(&fragment);

    // ReadPhysicalRecord may have only had an empty trailer remaining in its
    // internal buffer. Calculate the offset of the next physical record now
    // that it has returned, properly accounting for its header size.
    uint64_t physical_record_offset =
        end_of_buffer_offset_ - buffer_.size() - kHeaderSize - fragment.size();

    if (resyncing_) {
      if (record_type == kMiddleType) {
        continue;
      } else if (record_type == kLastType) {
        resyncing_ = false;
        continue;
      } else {
        resyncing_ = false;
      }
    }

    switch (record_type) {
      case kFullType:
        if (in_fragmented_record) {
          // Handle bug in earlier versions of log::Writer where
          // it could emit an empty kFirstType record at the tail end
          // of a block followed by a kFullType or kFirstType record
          // at the beginning of the next block.
          if (!scratch->empty()) {
            ReportCorruption(scratch->size(), "partial record without end(1)");
          }
        }
        prospective_record_offset = physical_record_offset;
        scratch->clear();
        *record = fragment;
        last_record_offset_ = prospective_record_offset;
        return true;

      case kFirstType:
        if (in_fragmented_record) {
          // Handle bug in earlier versions of log::Writer where
          // it could emit an empty kFirstType record at the tail end
          // of a block followed by a kFullType or kFirstType record
          // at the beginning of the next block.
          if (!scratch->empty()) {
            ReportCorruption(scratch->size(), "partial record without end(2)");
          }
        }
        prospective_record_offset = physical_record_offset;
        scratch->assign(fragment.data(), fragment.size());
        in_fragmented_record = true;
        break;

      case kMiddleType:
        if (!in_fragmented_record) {
          ReportCorruption(fragment.size(),
                           "missing start of fragmented record(1)");
        } else {
          scratch->append(fragment.data(), fragment.size());
        }
        break;

      case kLastType:
        if (!in_fragmented_record) {
          ReportCorruption(fragment.size(),
                           "missing start of fragmented record(2)");
        } else {
          scratch->append(fragment.data(), fragment.size());
          *record = Slice(*scratch);
          last_record_offset_ = prospective_record_offset;
          return true;
        }
        break;

      case kEof:
        if (in_fragmented_record) {
          // This can be caused by the writer dying immediately after
          // writing a physical record but before completing the next; don't
          // treat it as a corruption, just ignore the entire logical record.
          scratch->clear();
        }
        return false;

      case kBadRecord:
        if (in_fragmented_record) {
          ReportCorruption(scratch->size(), "error in middle of record");
          in_fragmented_record = false;
          scratch->clear();
        }
        break;

      default: {
        char buf[40];
        snprintf(buf, sizeof(buf), "unknown record type %u", record_type);
        ReportCorruption(
            (fragment.size() + (in_fragmented_record ? scratch->size() : 0)),
            buf);
        in_fragmented_record = false;
        scratch->clear();
        break;
      }
    }
  }
  return false;
}

unsigned int Reader::ReadPhysicalRecord(Slice* result) {
  while (true) {
    if (buffer_.size() < kHeaderSize) {
      if (!eof_) {
        // Last read was a full read, so this is a trailer to skip
        buffer_.clear();
		
		//从文件读one block,放入backing_store_
		//buffer_只是记录backing_store_的读取位置和所剩长度;
		//ReadPhysicalRecord的调用者ReadRecord相当于循环从backing_store_读记录,
		//当buffer_.size() < kHeaderSize 7时,就从实体文件读一个block(32K)
        Status status = file_->Read(kBlockSize, &buffer_, backing_store_);
        end_of_buffer_offset_ += buffer_.size();
        if (!status.ok()) {
          buffer_.clear();
          ReportDrop(kBlockSize, status);
          eof_ = true;
          return kEof;
        } else if (buffer_.size() < kBlockSize) {
          eof_ = true;
        }
        continue;
      } else {
        // Note that if buffer_ is non-empty, we have a truncated header at the
        // end of the file, which can be caused by the writer crashing in the
        // middle of writing the header. Instead of considering this an error,
        // just report EOF.
        buffer_.clear();
        return kEof;
      }
    }

    // Parse the header
    const char* header = buffer_.data();
    const uint32_t a = static_cast<uint32_t>(header[4]) & 0xff;
    const uint32_t b = static_cast<uint32_t>(header[5]) & 0xff;
    const unsigned int type = header[6];
    const uint32_t length = a | (b << 8);
    if (kHeaderSize + length > buffer_.size()) {
      size_t drop_size = buffer_.size();
      buffer_.clear();
      if (!eof_) {
        ReportCorruption(drop_size, "bad record length");
        return kBadRecord;
      }
      // If the end of the file has been reached without reading |length| bytes
      // of payload, assume the writer died in the middle of writing the record.
      // Don't report a corruption.
      return kEof;
    }

    if (type == kZeroType && length == 0) {
      // Skip zero length record without reporting any drops since
      // such records are produced by the mmap based writing code in
      // env_posix.cc that preallocates file regions.
      buffer_.clear();
      return kBadRecord;
    }

    // Check crc
    if (checksum_) {
      uint32_t expected_crc = crc32c::Unmask(DecodeFixed32(header));
      uint32_t actual_crc = crc32c::Value(header + 6, 1 + length);
      if (actual_crc != expected_crc) {
        // Drop the rest of the buffer since "length" itself may have
        // been corrupted and if we trust it, we could find some
        // fragment of a real log record that just happens to look
        // like a valid log record.
        size_t drop_size = buffer_.size();
        buffer_.clear();
        ReportCorruption(drop_size, "checksum mismatch");
        return kBadRecord;
      }
    }

    buffer_.remove_prefix(kHeaderSize + length);

    // Skip physical record that started before initial_offset_
    if (end_of_buffer_offset_ - buffer_.size() - kHeaderSize - length <
        initial_offset_) {
      result->clear();
      return kBadRecord;
    }

    *result = Slice(header + kHeaderSize, length);
    return type;
  }
}

ReadPhysicalRecord的调用者ReadRecord相当于循环从backing_store_读记录到scratch,buffer_记录backing_store_的读取位置和所剩长度,当buffer_.size() < kHeaderSize 7时,就从实体文件读一个block(32K)进backing_store_。其中还有一些CRC校验、类型判断、异常处理等。

注意buffer_(Slice)中没有实际数据,只有指向backing_store_(new char[kBlockSize])数据的指针,Slice的使用者保证在Slice的生命周期内外部数组是有效的。为什么不用直接用std::string,而是最后再把append到std::string里?mybe,每次读32K固定的数据,需要记录的是读取位置和剩余长度,slice和字符数组这样的组合 更适合这个场景。

6.总结

1.理解了log文件的结构,就很容易理解log读写的逻辑。

2.Slice这样看似简单的数据结构,初始自己感觉没有必要存在,仔细想想就会感觉到作者的设计精妙之处。

3.fsync/fdatasync 用或不用,可靠度和性能间取舍。

程序员之路,还是需要积累啊。ヾ(◍°∇°◍)ノ゙

leveldb varint 可变长整数

leveldb varint 可变长整数

在读leveldb时看到Varint这个东西,瞬间想起了自己做协议分析、XYHY的时光了。GOOGLE的另一个开源项目protobuf也有varint这个东东。许多软件的私有通讯协议也有用到varint。

1.简介

Varint 是一种紧凑的表示数字的方法。它用一个或多个字节来表示一个数字,值越小的数字使用越少的字节数。这能减少用来表示数字的字节数。

比如对于 int32 类型的数字,一般需要 4 个 byte 来表示。但是采用 Varint,对于很小的 int32 类型的数字,则可以用 1 个 byte 来表示。当然凡事都有好的也有不好的一面,采用 Varint 表示法,大的数字则需要 5 个 byte 来表示。从统计的角度来说,一般不会所有的消息中的数字都是大数,因此大多数情况下,采用 Varint 后,可以用更少的字节数来表示数字信息。Varint 中的每个 byte 的最高位 bit 有特殊的含义,如果该位为 1,表示后续的 byte 也是该数字的一部分,如果该位为 0,则结束。

 

简单来说,可变长的整数,每个字节的最高位标识后续的byte是否还是该数字的一部分

因为所用到的数字(表示长度或者表示其他)往往比较小,用可变长整数信息的表示非常紧凑,自然需要更少的资源。比如(protobuf应用)网络上传输的字节数更少,需要的 IO 更少;(protobuf 或 leveldb)存盘的所用空间更少

Read More Read More

Leveldb源码 skiplist 跳表

Leveldb源码 skiplist 跳表

概述

跳表是一种有序数据结构,它通过在每个节点维持多个指向其他节点的指针,从而达到快速访问节点的目的。

跳表基于并联的链表,其效率可比拟于二叉查找树(对于大多数操作需要O(log n)平均时间)。

插入新节点时,该节点层数随机。

更详尽的解释参见维基百科或自行google。贴两张维基百科的图片,便于大家理解。

大家有兴趣也可以去看redis的skiplist实现(zskiplist)。

Read More Read More

Leveldb源码 Arena 内存池

Leveldb源码 Arena 内存池

概述

一个高性能的服务器端程序,内存的使用非常重要。多次的申请和释放引起的内存碎片,一旦碎片到达一定程度,即使剩余内存总量够用,但由于缺乏足够的连续空闲空间,导致内存不够用的假象。为了避免小块内存的频繁分配,最简单的做法就是申请大块的内存,多次分给客户。

一般的策略都是:
小块内存–>从内存池里拿;不够的话,内存池向系统申请新的大块。
大块内存–>直接问系统拿。

如果对这块感兴趣可以自行研究一下:ptmalloc、tcmalloc、Jemalloc、Nginx内存池。

Redis默认使用jemalloc,我们公司的项目也是使用jemalloc。

Redis的Makefile片段:

# Default allocator
ifeq ($(uname_S),Linux)
	MALLOC=jemalloc
else
	MALLOC=libc
endif

# Backwards compatibility for selecting an allocator
ifeq ($(USE_TCMALLOC),yes)
	MALLOC=tcmalloc
endif

ifeq ($(USE_TCMALLOC_MINIMAL),yes)
	MALLOC=tcmalloc_minimal
endif

ifeq ($(USE_JEMALLOC),yes)
	MALLOC=jemalloc
endif

ifeq ($(USE_JEMALLOC),no)
	MALLOC=libc
endif

好,言归正传。leveldb中实现了一个”一次性”的简单的内存池Arena,不是所有的地方都使用了这个内存池,主要是memtable(skiplist)使用

Read More Read More

leveldb原理剖析

leveldb原理剖析

最近在读leveldb源码,发现了这篇文章,感觉蛮不错,转载了过来。

转载:https://www.ezlippi.com/blog/2014/11/leveldb.html

 

在说LevelDb之前,先认识两位大牛,Jeff Dean和Sanjay Ghemawat,这两位是Google公司重量级的工程师,为数甚少的Google Fellow之二。

Jeff Dean其人:http://research.google.com/people/jeff/index.html,Google大规模分布式平台Bigtable和MapReduce主要设计和实现者。

Sanjay Ghemawat其人:http://research.google.com/people/sanjay/index.html,Google大规模分布式平台GFS,Bigtable和MapReduce主要设计和实现工程师。

LevelDb就是这两位大神级别的工程师发起的开源项目,简而言之,LevelDb是能够处理十亿级别规模Key-Value型数据持久性存储的C++ 程序库。正像上面介绍的,这二位是Bigtable的设计和实现者,如果了解Bigtable的话,应该知道在这个影响深远的分布式存储系统中有两个核心的部分:Master Server和Tablet Server。其中Master Server做一些管理数据的存储以及分布式调度工作,实际的分布式数据存储以及读写操作是由Tablet Server完成的,而LevelDb则可以理解为一个简化版的Tablet Server。

Read More Read More

Hash 散列函数

Hash 散列函数

今天读leveldb代码,看到murmur散列方法,突然想起以前公司关于hash的故事。所在产品线的一套代码十几年,一直在维护,新需求来了就是在上面增加模块,不带第三方库毫不夸张几十万行,记得某个文件没重构之前3w行。经手的人一多,加上产品线平台基础库推广力度不够,就是各种造轮子。



其中用的最多的哈希表 初始化是这个样子的,(当然hash表的实现也很多) :


//** bucket_cnt     :桶的个数
//** hash_key_func_t:哈希函数指针
//** hash_compare_t :键值比较函数指针
//** hash_destroy_func_t:释放节点中data数据的函数指针
//** hash_nodesize_cnt_t:哈希节点占用内存大小计算函数指针
//** bucket_depth	:桶的深度,设置为0表示不做限制
//**************************************************************************
hash_t *hash_init (	int	bucket_cnt, 
						hash_key_func_t     key_func, 
						hash_compare_t      compare_func,
						hash_destroy_func_t destroy_node_func,
						hash_nodesize_cnt_t nodesize_cnt_func = NULL,
						int	bucket_depth = 0);



感觉接口设计挺好的,但,hash函数需要自己实现,导致系统种各种散列函数的存在,加乘异或移位,其中当然有好的实现,但是那么一两个我竟然看到了&,为什么没出事我也不太清楚,可能是数据不多。



某一天,系统(DPDK收包然后处理)出现丢包现象,最后的定位问题是哈希表散列性不好,导致某些桶特别深,查询出现热点,相当于在一个相当长的list上遍历比较,一直返回不了,数据量一大就出现丢包,最后修改散列函数后改善。此事之后凡是用到哈希表,单元测试都要求对其随机分布性做测试。

Leveldb使用的murmur hash变种,redis也有用到murmur hash。

MurmurHash 是一种非加密哈希函数,适用于一般的哈希检索操作。由Austin Appleby在2008年发明,并出现了多个变种,都已经发布到了公有领域(public domain)。与其它流行的哈希函数相比,对于规律性较强的key,MurmurHash的随机分布特征表现更良好。–wiki

在这里贴一下leveldb的源码:

#ifndef FALLTHROUGH_INTENDED
#define FALLTHROUGH_INTENDED do { } while (0)
#endif

namespace leveldb {

uint32_t Hash(const char* data, size_t n, uint32_t seed) {
  // Similar to murmur hash
  const uint32_t m = 0xc6a4a793;
  const uint32_t r = 24;
  const char* limit = data + n;
  uint32_t h = seed ^ (n * m);

  // Pick up four bytes at a time
  while (data + 4 <= limit) {
    uint32_t w = DecodeFixed32(data);
    data += 4;
    h += w;
    h *= m;
    h ^= (h >> 16);
  }

  // Pick up remaining bytes
  switch (limit - data) {
    case 3:
      h += static_cast<unsigned char>(data[2]) << 16;
      FALLTHROUGH_INTENDED;
    case 2:
      h += static_cast<unsigned char>(data[1]) << 8;
      FALLTHROUGH_INTENDED;
    case 1:
      h += static_cast<unsigned char>(data[0]);
      h *= m;
      h ^= (h >> r);
      break;
  }
  return h;
}


}  // namespace leveldb

C 结构体初始化

C 结构体初始化

1.前言

今天阅读linux kernel oom代码,看到一种结构体初始化方式,原来没见过,记录一下。

//结构体定义
struct oom_control {
	/* Used to determine cpuset */
	struct zonelist *zonelist;

	/* Used to determine mempolicy */
	nodemask_t *nodemask;

	/* Memory cgroup in which oom is invoked, or NULL for global oom */
	struct mem_cgroup *memcg;

	/* Used to determine cpuset and node locality requirement */
	const gfp_t gfp_mask;

	/*
	 * order == -1 means the oom kill is required by sysrq, otherwise only
	 * for display purposes.
	 */
	const int order;

	/* Used by oom implementation, do not set */
	unsigned long totalpages;
	struct task_struct *chosen;
	unsigned long chosen_points;
};
//初始化方式
struct oom_control oc = {
	.zonelist = NULL,
	.nodemask = NULL,
	.memcg = NULL,
	.gfp_mask = 0,
	.order = 0,
};

2.struct四种初始化的方式

初始化方式1: 定义时赋值(不可乱序,不可缺省)
初始化方式2: 定义后赋值
初始化方式3: 定义时赋值(可乱序 可缺省. 点号)
初始化方式4: 定义时赋值(可乱序 可缺省 : 冒号)

//测试代码
#include <stdlib.h>
#include <stdio.h>

struct test_struct {

	int    a;
	char*   p;
};

int main()
{
	struct test_struct imp;
	imp.a = 100;
	imp.p = "hello world100";

	struct test_struct imp0 = {
		.a = 0,
		.p = "hello world0"
		};
	struct test_struct imp1 = {
		a : 1,
		p : "hello world1"
	};
	struct test_struct imp2 = {2, "hello world2"};

	printf("imp  a:%d  p: %s\n", imp.a, imp.p);
	printf("imp0 a:%d  p: %s\n", imp0.a, imp0.p);
	printf("imp1 a:%d  p: %s\n", imp1.a, imp1.p);
	printf("imp2 a:%d  p: %s\n", imp2.a, imp2.p);
	
	return 0;
}

3.总结

相比顺序初始化而言,乱序初始化成员可以不按照顺序初始化,而且可以只初始化部分成员,乱序初始化有两种方式,一种是用点(.)符号,一种是用冒号(:)。

参考:https://gcc.gnu.org/onlinedocs/gcc/Designated-Inits.html

STL vector 扩容

STL vector 扩容

昨天面试,面试官问到一个问题,vector怎么扩容的,我大概记得C++ premier有那么一句扩两倍。我说好像是扩两倍,面试官也没继续问也没反馈对错。甚是好奇对错,索性自己试验一把,并看下源码。

试验

代码

#include<iostream>
#include<vector>
using namespace std;

int main(int argc, char *argv[])
{
	vector<int> vInt;

	for(int i = 0; i < 100; i++ )
	{
		cout << "size:" << vInt.size() << "\t" << "capacity:" << vInt.capacity() << endl;
		vInt.push_back(1);
	}

	return 0;
}

输出

size:0	capacity:0
size:1	capacity:1
size:2	capacity:2
size:3	capacity:4
size:4	capacity:4
size:5	capacity:8
size:6	capacity:8
size:7	capacity:8
size:8	capacity:8
size:9	capacity:16
size:10	capacity:16
size:11	capacity:16
size:12	capacity:16
size:13	capacity:16
size:14	capacity:16
size:15	capacity:16
size:16	capacity:16
size:17	capacity:32
size:18	capacity:32
......

源码

在这只把扩容相关代码贴出来罢了。

//SGI STL v3.3
void push_back(const _Tp& __x) {
if (_M_finish != _M_end_of_storage) {
  construct(_M_finish, __x);
  ++_M_finish;
}
else
  _M_insert_aux(end(), __x);
}

iterator insert(iterator __position, const _Tp& __x) {
size_type __n = __position - begin();
if (_M_finish != _M_end_of_storage && __position == end()) {
  construct(_M_finish, __x);
  ++_M_finish;
}
else
  _M_insert_aux(__position, __x);
return begin() + __n;
}

template <class _Tp, class _Alloc>
void 
vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x)
{
  if (_M_finish != _M_end_of_storage) {
    construct(_M_finish, *(_M_finish - 1));
    ++_M_finish;
    _Tp __x_copy = __x;
    copy_backward(__position, _M_finish - 2, _M_finish - 1);
    *__position = __x_copy;
  }
  else {
    const size_type __old_size = size();
    //原容量为0扩为1,否则扩为原2倍
    const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
    iterator __new_start = _M_allocate(__len);
    iterator __new_finish = __new_start;
    __STL_TRY {
      __new_finish = uninitialized_copy(_M_start, __position, __new_start);
      construct(__new_finish, __x);
      ++__new_finish;
      __new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
    }
    __STL_UNWIND((destroy(__new_start,__new_finish), 
                  _M_deallocate(__new_start,__len)));
    destroy(begin(), end());
    _M_deallocate(_M_start, _M_end_of_storage - _M_start);
    _M_start = __new_start;
    _M_finish = __new_finish;
    _M_end_of_storage = __new_start + __len;
  }
}

在push_back或者inster的时候,vetor容量不够扩容为原长度两倍。
这个增长因子和各版本STL实现有关,有的版本用1.5

为什么是扩为原长度2倍

因为每次扩容都涉及到原来元素的copy。空间和时间的权衡。
简单来说, 空间分配的多,平摊时间复杂度低,但浪费空间也多。
具体参见算法导论中,平摊分析那一章关于动态表扩张的分析。