随笔 - 93  文章 - 0  trackbacks - 0
<2020年1月>
2930311234
567891011
12131415161718
19202122232425
2627282930311
2345678

常用链接

留言簿

随笔分类

随笔档案

收藏夹

调试技巧

搜索

  •  

最新评论

阅读排行榜

评论排行榜

60天内阅读排行

1.何为队列

听到队列相信大家对其并不陌生,在我们现实生活中队列随处可见,去超市结账,你会看见大家都会一排排的站得好好的,等待结账,为什么要站得一排排的,你想象一下大家都没有素质,一窝蜂的上去结账,不仅让这个超市崩溃,还会容易造成各种踩踏事件,当然这些事其实在我们现实中也是会经常发生。

当然在计算机世界中,队列是属于一种数据结构,队列采用的FIFO(first in firstout),新元素(等待进入队列的元素)总是被插入到尾部,而读取的时候总是从头部开始读取。在计算中队列一般用来做排队(如线程池的等待排队,锁的等待排队),用来做解耦(生产者消费者模式),异步等等。

2.jdk中的队列

在jdk中的队列都实现了java.util.Queue接口,在队列中又分为两类,一类是线程不安全的,ArrayDeque,LinkedList等等,还有一类都在java.util.concurrent包下属于线程安全,而在我们真实的环境中,我们的机器都是属于多线程,当多线程对同一个队列进行排队操作的时候,如果使用线程不安全会出现,覆盖数据,数据丢失等无法预测的事情,所以我们这个时候只能选择线程安全的队列。在jdk中提供的线程安全的队列下面简单列举部分队列:

队列名字 是否加锁 数据结构 关键技术点 是否有锁 是否有界
ArrayBlockingQueue 数组array ReentrantLock 有锁 有界
LinkedBlockingQueue 链表 ReentrantLock 有锁 有界
LinkedTransferQueue 链表 CAS 无锁 无界
ConcurrentLinkedQueue 链表 CAS 无锁 无界

我们可以看见,我们无锁的队列是无界的,有锁的队列是有界的,这里就会涉及到一个问题,我们在真正的线上环境中,无界的队列,对我们系统的影响比较大,有可能会导致我们内存直接溢出,所以我们首先得排除无界队列,当然并不是无界队列就没用了,只是在某些场景下得排除。其次还剩下ArrayBlockingQueue,LinkedBlockingQueue两个队列,他们两个都是用ReentrantLock控制的线程安全,他们两个的区别一个是数组,一个是链表,在队列中,一般获取这个队列元素之后紧接着会获取下一个元素,或者一次获取多个队列元素都有可能,而数组在内存中地址是连续的,在操作系统中会有缓存的优化(下面也会介绍缓存行),所以访问的速度会略胜一筹,我们也会尽量去选择ArrayBlockingQueue。而事实证明在很多第三方的框架中,比如早期的log4j异步,都是选择的ArrayBlockingQueue。

当然ArrayBlockingQueue,也有自己的弊端,就是性能比较低,为什么jdk会增加一些无锁的队列,其实就是为了增加性能,很苦恼,又需要无锁,又需要有界,这个时候恐怕会忍不住说一句你咋不上天呢?但是还真有人上天了。

3.Disruptor

Disruptor就是上面说的那个天,Disruptor是英国外汇交易公司LMAX开发的一个高性能队列,并且是一个开源的并发框架,并获得2011Duke’s程序框架创新奖。能够在无锁的情况下实现网络的Queue并发操作,基于Disruptor开发的系统单线程能支撑每秒600万订单。目前,包括Apache Storm、Camel、Log4j2等等知名的框架都在内部集成了Disruptor用来替代jdk的队列,以此来获得高性能。

3.1为什么这么牛逼?

上面已经把Disruptor吹出了花了,你肯定会产生疑问,他真的能有这么牛逼吗,我的回答是当然的,在Disruptor中有三大杀器:

  • CAS
  • 消除伪共享
  • RingBuffer 有了这三大杀器,Disruptor才变得如此牛逼。

3.1.1锁和CAS

我们ArrayBlockingQueue为什么会被抛弃的一点,就是因为用了重量级lock锁,在我们加锁过程中我们会把锁挂起,解锁后,又会把线程恢复,这一过程会有一定的开销,并且我们一旦没有获取锁,这个线程就只能一直等待,这个线程什么事也不能做。

CAS(compare and swap),顾名思义先比较在交换,一般是比较是否是老的值,如果是的进行交换设置,大家熟悉乐观锁的人都知道CAS可以用来实现乐观锁,CAS中没有线程的上下文切换,减少了不必要的开销。 这里使用JMH,用两个线程,每次1一次调用,在我本机上进行测试,代码如下:

@BenchmarkMode({Mode.SampleTime}) @OutputTimeUnit(TimeUnit.MILLISECONDS) @Warmup(iterations=3, time = 5, timeUnit = TimeUnit.MILLISECONDS) @Measurement(iterations=1,batchSize = 100000000) @Threads(2) @Fork(1) @State(Scope.Benchmark) public class Myclass {     Lock lock = new ReentrantLock();     long i = 0;     AtomicLong atomicLong = new AtomicLong(0);     @Benchmark     public void measureLock() {         lock.lock();         i++;         lock.unlock();     }     @Benchmark     public void measureCAS() {         atomicLong.incrementAndGet();     }     @Benchmark     public void measureNoLock() {         i++;     } } 复制代码

测试出来结果如下:

测试项目 测试结果
Lock 26000ms
CAS 4840ms
无锁 197ms

可以看见Lock是五位数,CAS是四位数,无锁更小是三位数。 由此我们可以知道Lock>CAS>无锁。

而我们的Disruptor中使用的就是CAS,他利用CAS进行队列中的一些下标设置,减少了锁的冲突,提高了性能。

另外对于jdk中其他的无锁队列也是使用CAS,原子类也是使用CAS。

3.1.2伪共享

谈到了伪共享就不得不说计算机CPU缓存,缓存大小是CPU的重要指标之一,而且缓存的结构和大小对CPU速度的影响非常大,CPU内缓存的运行频率极高,一般是和处理器同频运作,工作效率远远大于系统内存和硬盘。实际工作时,CPU往往需要重复读取同样的数据块,而缓存容量的增大,可以大幅度提升CPU内部读取数据的命中率,而不用再到内存或者硬盘上寻找,以此提高系统性能。但是从CPU芯片面积和成本的因素来考虑,缓存都很小。

 

 

CPU缓存可以分为一级缓存,二级缓存,如今主流CPU还有三级缓存,甚至有些CPU还有四级缓存。每一级缓存中所储存的全部数据都是下一级缓存的一部分,这三种缓存的技术难度和制造成本是相对递减的,所以其容量也是相对递增的。

为什么CPU会有L1、L2、L3这样的缓存设计?主要是因为现在的处理器太快了,而从内存中读取数据实在太慢(一个是因为内存本身速度不够,另一个是因为它离CPU太远了,总的来说需要让CPU等待几十甚至几百个时钟周期),这个时候为了保证CPU的速度,就需要延迟更小速度更快的内存提供帮助,而这就是缓存。对这个感兴趣可以把电脑CPU拆下来,自己把玩一下。

每一次你听见intel发布新的cpu什么,比如i7-7700k,8700k,都会对cpu缓存大小进行优化,感兴趣可以自行下来搜索,这些的发布会或者发布文章。

Martin和Mike的 QConpresentation演讲中给出了一些每个缓存时间:

从CPU到 大约需要的CPU周期 大约需要的时间
主存 约60-80纳秒
QPI 总线传输(between sockets, not drawn) 约20ns
L3 cache 约40-45 cycles 约15ns
L2 cache 约10 cycles 约3ns
L1 cache 约3-4 cycles 约1ns
寄存器 1 cycle

缓存行

在cpu的多级缓存中,并不是以独立的项来保存的,而是类似一种pageCahe的一种策略,以缓存行来保存,而缓存行的大小通常是64字节,在Java中Long是8个字节,所以可以存储8个Long,举个例子,你访问一个long的变量的时候,他会把帮助再加载7个,我们上面说为什么选择数组不选择链表,也就是这个原因,在数组中可以依靠缓冲行得到很快的访问。

 

缓存行是万能的吗?NO,因为他依然带来了一个缺点,我在这里举个例子说明这个缺点,可以想象有个数组队列,ArrayQueue,他的数据结构如下:

class ArrayQueue{     long maxSize;     long currentIndex; } 复制代码

对于maxSize是我们一开始就定义好的,数组的大小,对于currentIndex,是标志我们当前队列的位置,这个变化比较快,可以想象你访问maxSize的时候,是不是把currentIndex也加载进来了,这个时候,其他线程更新currentIndex,就会把cpu中的缓存行置位无效,请注意这是CPU规定的,他并不是只吧currentIndex置位无效,如果此时又继续访问maxSize他依然得继续从内存中读取,但是MaxSize却是我们一开始定义好的,我们应该访问缓存即可,但是却被我们经常改变的currentIndex所影响。

 

 

Padding的魔法

为了解决上面缓存行出现的问题,在Disruptor中采用了Padding的方式,

class LhsPadding {     protected long p1, p2, p3, p4, p5, p6, p7; }  class Value extends LhsPadding {     protected volatile long value; }  class RhsPadding extends Value {     protected long p9, p10, p11, p12, p13, p14, p15; } 复制代码

其中的Value就被其他一些无用的long变量给填充了。这样你修改Value的时候,就不会影响到其他变量的缓存行。

最后顺便一提,在jdk8中提供了@Contended的注解,当然一般来说只允许Jdk中内部,如果你自己使用那就得配置Jvm参数 -RestricContentended = fase,将限制这个注解置位取消。很多文章分析了ConcurrentHashMap,但是都把这个注解给忽略掉了,在ConcurrentHashMap中就使用了这个注解,在ConcurrentHashMap每个桶都是单独的用计数器去做计算,而这个计数器由于时刻都在变化,所以被用这个注解进行填充缓存行优化,以此来增加性能。

 

 

3.1.3RingBuffer

在Disruptor中采用了数组的方式保存了我们的数据,上面我们也介绍了采用数组保存我们访问时很好的利用缓存,但是在Disruptor中进一步选择采用了环形数组进行保存数据,也就是RingBuffer。在这里先说明一下环形数组并不是真正的环形数组,在RingBuffer中是采用取余的方式进行访问的,比如数组大小为 10,0访问的是数组下标为0这个位置,其实10,20等访问的也是数组的下标为0的这个位置。

实际上,在这些框架中取余并不是使用%运算,都是使用的&与运算,这就要求你设置的大小一般是2的N次方也就是,10,100,1000等等,这样减去1的话就是,1,11,111,就能很好的使用index & (size -1),这样利用位运算就增加了访问速度。 如果在Disruptor中你不用2的N次方进行大小设置,他会抛出buffersize必须为2的N次方异常。

当然其不仅解决了数组快速访问的问题,也解决了不需要再次分配内存的问题,减少了垃圾回收,因为我们0,10,20等都是执行的同一片内存区域,这样就不需要再次分配内存,频繁的被JVM垃圾回收器回收。

 

 

自此三大杀器已经说完了,有了这三大杀器为Disruptor如此高性能垫定了基础。接下来还会在讲解如何使用Disruptor和Disruptor的具体的工作原理。

3.2Disruptor怎么使用

下面举了一个简单的例子:

ublic static void main(String[] args) throws Exception {         // 队列中的元素         class Element {             @Contended             private String value;               public String getValue() {                 return value;             }              public void setValue(String value) {                 this.value = value;             }         }          // 生产者的线程工厂         ThreadFactory threadFactory = new ThreadFactory() {             int i = 0;             @Override             public Thread newThread(Runnable r) {                 return new Thread(r, "simpleThread" + String.valueOf(i++));             }         };          // RingBuffer生产工厂,初始化RingBuffer的时候使用         EventFactory<Element> factory = new EventFactory<Element>() {             @Override             public Element newInstance() {                 return new Element();             }         };          // 处理Event的handler         EventHandler<Element> handler = new EventHandler<Element>() {             @Override             public void onEvent(Element element, long sequence, boolean endOfBatch) throws InterruptedException {                 System.out.println("Element: " + Thread.currentThread().getName() + ": " + element.getValue() + ": " + sequence); //                Thread.sleep(10000000);             }         };           // 阻塞策略         BlockingWaitStrategy strategy = new BlockingWaitStrategy();          // 指定RingBuffer的大小         int bufferSize = 8;          // 创建disruptor,采用单生产者模式         Disruptor<Element> disruptor = new Disruptor(factory, bufferSize, threadFactory, ProducerType.SINGLE, strategy);          // 设置EventHandler         disruptor.handleEventsWith(handler);          // 启动disruptor的线程         disruptor.start();         for (int i = 0; i < 10; i++) {             disruptor.publishEvent((element, sequence) -> {                 System.out.println("之前的数据" + element.getValue() + "当前的sequence" + sequence);                 element.setValue("我是第" + sequence + "个");             });          }     } 复制代码

在Disruptor中有几个比较关键的: ThreadFactory:这是一个线程工厂,用于我们Disruptor中生产者消费的时候需要的线程。 EventFactory:事件工厂,用于产生我们队列元素的工厂,在Disruptor中,他会在初始化的时候直接填充满RingBuffer,一次到位。 EventHandler:用于处理Event的handler,这里一个EventHandler可以看做是一个消费者,但是多个EventHandler他们都是独立消费的队列。 WorkHandler:也是用于处理Event的handler,和上面区别在于,多个消费者都是共享同一个队列。 WaitStrategy:等待策略,在Disruptor中有多种策略,来决定消费者获消费时,如果没有数据采取的策略是什么?下面简单列举一下Disruptor中的部分策略

  • BlockingWaitStrategy:通过线程阻塞的方式,等待生产者唤醒,被唤醒后,再循环检查依赖的sequence是否已经消费。

  • BusySpinWaitStrategy:线程一直自旋等待,可能比较耗cpu

  • LiteBlockingWaitStrategy:线程阻塞等待生产者唤醒,与BlockingWaitStrategy相比,区别在signalNeeded.getAndSet,如果两个线程同时访问一个访问waitfor,一个访问signalAll时,可以减少lock加锁次数.

  • LiteTimeoutBlockingWaitStrategy:与LiteBlockingWaitStrategy相比,设置了阻塞时间,超过时间后抛异常。

  • YieldingWaitStrategy:尝试100次,然后Thread.yield()让出cpu

EventTranslator:实现这个接口可以将我们的其他数据结构转换为在Disruptor中流通的Event。

3.3工作原理

上面已经介绍了CAS,减少伪共享,RingBuffer三大杀器,介绍下来说一下Disruptor中生产者和消费者的整个流程。

3.3.1生产者

对于生产者来说,可以分为多生产者和单生产者,用ProducerType.Single,和ProducerType.MULTI区分,多生产者和单生产者来说多了CAS,因为单生产者由于是单线程,所以不需要保证线程安全。

在disruptor中通常用disruptor.publishEvent和disruptor.publishEvents()进行单发和群发。

在disruptor发布一个事件进入队列需要下面几个步骤:

  1. 首先获取RingBuffer中下一个在RingBuffer上可以发布的位置,这个可以分为两类:
  • 从来没有写过的位置
  • 已经被所有消费者读过,可以在写的位置。 如果没有读取到会一直尝试去读,disruptor做的很巧妙,并没有一直占据CPU,而是通过LockSuport.park(),进行了一下将线程阻塞挂起操作,为的是不让CPU一直进行这种空循环,不然其他线程都抢不到CPU时间片。
    获取位置之后会进行cas进行抢占,如果是单线程就不需要。
  1. 接下来调用我们上面所介绍的EventTranslator将第一步中RingBuffer中那个位置的event交给EventTranslator进行重写。
  2. 进行发布,在disruptor还有一个额外的数组用来记录当前ringBuffer所在位置目前最新的序列号是多少,拿上面那个0,10,20举例,写到10的时候这个avliableBuffer就在对应的位置上记录目前这个是属于10,有什么用呢后面会介绍。进行发布的时候需要更新这个avliableBuffer,然后进行唤醒所有阻塞的生产者。

下面简单画一下流程,上面我们拿10举例是不对的,因为bufferSize必须要2的N次方,所以我们这里拿Buffersize=8来举例:下面介绍了当我们已经push了8个event也就是一圈的时候,接下来再push 3条消息的一些过程: 1.首先调用next(3),我们当前在7这个位置上所以接下来三条是8,9,10,取余也就是0,1,2。 2.重写0,1,2这三个内存区域的数据。 3.写avaliableBuffer。

 

 

对了不知道大家对上述流程是不是很熟悉呢,对的那就是类似我们的2PC,两阶段提交,先进行RingBuffer的位置锁定,然后在进行提交和通知消费者。具体2PC的介绍可以参照我的另外一篇文章再有人问你分布式事务,给他看这篇文章

3.3.1消费者

对于消费者来说,上面介绍了分为两种,一种是多个消费者独立消费,一种是多个消费者消费同一个队列,这里介绍一下较为复杂的多个消费者消费同一个队列,能理解这个也就能理解独立消费。 在我们的disruptor.strat()方法中会启动我们的消费者线程以此来进行后台消费。在消费者中有两个队列需要我们关注,一个是所有消费者共享的进度队列,还有个是每个消费者独立消费进度队列。 1.对消费者共享队列进行下一个Next的CAS抢占,以及对自己消费进度的队列标记当前进度。 2.为自己申请可读的RingBuffer的Next位置,这里的申请不仅仅是申请到next,有可能会申请到比Next大的一个范围,阻塞策略的申请的过程如下:

  • 获取生产者对RingBuffer最新写的位置
  • 判断其是否小于我要申请读的位置
  • 如果大于则证明这个位置已经写了,返回给生产者。
  • 如果小于证明还没有写到这个位置,在阻塞策略中会进行阻塞,其会在生产者提交阶段进行唤醒。 3.对这个位置进行可读校验,因为你申请的位置可能是连续的,比如生产者目前在7,接下来申请读,如果消费者已经把8和10这个序列号的位置写进去了,但是9这个位置还没来得及写入,由于第一步会返回10,但是9其实是不能读的,所以得把位置向下收缩到8。
    4.如果收缩完了之后比当前next要小,则继续循环申请。 5.交给handler.onEvent()处理

一样的我们举个例子,我们要申请next=8这个位置。 1.首先在共享队列抢占进度8,在独立队列写入进度7 2.获取8的可读的最大位置,这里根据不同的策略进行,我们选择阻塞,由于生产者生产了8,9,10,所以返回的是10,这样和后续就不需要再次和avaliableBuffer进行对比了。 3.最后交给handler进行处理。

 

4.Log4j中的Disruptor

下面的图展现了Log4j使用Disruptor,ArrayBlockingQueue以及同步的Log4j吞吐量的对比,可以看见使用了Disruptor完爆了其他的,当然还有更多的框架使用了Disruptor,这里就不做介绍了。

 

 


作者:咖啡拿铁
链接:https://juejin.im/post/5b5f10d65188251ad06b78e3
来源:掘金
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
posted @ 2020-01-16 20:12 长戟十三千 阅读(7) | 评论 (0)编辑 收藏
1、共享内存实现跨进程消息队列:《UNIX网络编程卷2》,消息队列,p85
      offset识别结构体内容,防止重复加载内存地址变更。共享信号量或者无锁环形队列,MAGIC NUMBER 验证,防止版本不一致。

2、虚拟实时:《linux内核设计与实现》, 进程调度,p43
      调度时使用时间记账。虚拟运行时间 +=加权(上一帧运行时间); while {run get_task( min(虚拟运行时间) ) ;}(true);
     移动检测时曾用到过异常移动的加权算法,与这个类似。每步移动异常加权,总量超过后,执行 禁止移动时间=异常总量/速度 的惩罚。

3、等待队列:《linux内核设计与实现》, 进程调度,p50
   在读列上自旋,没有事件则调度等待,否则返回。

epoll源码:自旋锁+就绪队列,mutex+红黑树数据
无限法则服务器:接口->协程+rpc->服务组件, 可灰更微服务,共享内存1s拉起,接口自动测试,全局锁服务器用于独占某些服务或操作。
ECS模式:word=system+entity; system=sys1+sys2+sysn; entity=componentN;
位标记的静态数组:int info_flg; T vct_info; 《linux内核设计与实现》, 软中断,p111。 tasklet:利用静态软中断,添加调度策略:高低优先级链表。ksoftirqd:每个cpu上低优先级内核线程池,处理高并发软中断,防止造成用户线程饥饿。
posted @ 2020-01-16 16:32 长戟十三千 阅读(14) | 评论 (0)编辑 收藏
     摘要: inline是C++关键字,在函数声明或定义中,函数返回类型前加上关键字inline,即可以把函数指定为内联函数。这样可以解决一些频繁调用的函数大量消耗栈空间(栈内存)的问题。关键字inline必须与函数定义放在一起才能使函数成为内联函数,仅仅将inline放在函数声明前面不起任何作用。inline是一种“用于实现”的关键字,而不是一种“用于声明”的...  阅读全文
posted @ 2020-01-13 11:28 长戟十三千 阅读(5) | 评论 (0)编辑 收藏
     摘要: 3)下面的函数被用来计算某个整数的平方,它能实现预期设计目标吗?如果不能,试回答存在什么问题:1234int square(volatile int *ptr){    return ((*ptr) * (*ptr));}3)这段代码是个恶作剧。这段代码的目的是用来返指针*ptr指向值的平方,但是,...  阅读全文
posted @ 2020-01-13 11:22 长戟十三千 阅读(6) | 评论 (0)编辑 收藏

前言

字节对齐是我们初学C语言就会接触到的一个概念,但是到底什么是字节对齐?对齐准则又是什么?为什么要字节对齐呢?字节对齐对我们编程有什么启示?本文将简单理一理字节对齐的那些事。

什么是字节对齐

计算机中内存大小的基本单位是字节(byte),理论上来讲,可以从任意地址访问某种基本数据类型,但是实际上,计算机并非逐字节大小读写内存,而是以2,4,或8的 倍数的字节块来读写内存,如此一来就会对基本数据类型的合法地址作出一些限制,即它的地址必须是2,4或8的倍数。那么就要求各种数据类型按照一定的规则在空间上排列,这就是对齐。

对齐准则是什么

总的来说,字节对齐有以下准则:

  • 结构体变量的首地址能够被其对齐字节数大小所整除
  • 结构体每个成员相对结构体首地址的偏移都是成员大小的整数倍,如不满足,对前一个成员填充字节以满足。
  • 结构体的总大小为结构体对齐字节数大小的整数倍,如不满足,最后填充字节以满足。

我们通过一个小例子来说明是如何对齐的。
考虑下面的程序

/*================================================================ *   Copyright (C) 2018  Ltd. All rights reserved. *    *   文件名称:testByteAlign.c *   创 建 者:shouwang *   创建日期:2018年09月15日 *   描    述: * ================================================================*/ #include<stdio.h> #include<stdint.h> struct test {     int a;     char b;     int c;     short d; }; int main(int argc,char *argv) {     /*在32位和64位的机器上,size_t的大小不同*/     printf("the size of struct test is %zu\n",sizeof(struct test));     return 0; } 

编译成32位程序并运行(默认四字节自然对齐),可以看到,结构体test 的大小为16字节,而不是11字节(a占4字节,b占1字节,c占4字节,d占2字节)

#64位机器上编译32位程序可能需要安装一个库 #sudo apt-get install gcc-multilib gcc -m32 -o testByteAlign testByteAlign.c #编译程序 chmod +x testByteAlign  #赋执行权限 ./testByteAlign  #运行 the size of struct test is 16 

实际上,结构体test的成员在内存中可能是像下面这样分布的(数值为偏移量)
未对齐时:

0~345~910~11abcd

对齐时:

0~345~78~1112~1314~15ab填充内容cd填充内容

从上面可以看出,c的偏移为5,不满足对齐要求(它的偏移量应该能够被sizeof(int)大小整除),因此在b后面填充了3个字节,使得c的偏移为8。在b后面填充后,d已经满足对齐要求了,为什么最后还要填充字节呢?或者说,为什么需要满足第三条准则呢?
考虑下面的声明

struct teArray[2]; 

我们不难知道,teArray[0]的d如果不填充字节,那么teArray[1]的a偏移为14,不满足对齐要求,因此d后面也需要填充字节。

为什么要字节对齐

无论数据是否对齐,大多数计算机还是能够正确工作,而且从前面可以看到,结构体test本来只需要11字节的空间,最后却占用了16字节,很明显浪费了空间,那么为什么还要进行字节对齐呢?最重要的考虑是提高内存系统性能
前面我们也说到,计算机每次读写一个字节块,例如,假设计算机总是从内存中取8个字节,如果一个double数据的地址对齐成8的倍数,那么一个内存操作就可以读或者写,但是如果这个double数据的地址没有对齐,数据就可能被放在两个8字节块中,那么我们可能需要执行两次内存访问,才能读写完成。显然在这样的情况下,是低效的。所以需要字节对齐来提高内存系统性能。
在有些处理器中,如果需要未对齐的数据,可能不能够正确工作甚至crash,这里我们不多讨论。

实际编程中的考虑

实际上,字节对齐的细节都由编译器来完成,我们不需要特意进行字节的对齐,但并不意味着我们不需要关注字节对齐的问题。

空间存储

还是考虑前面的结构体test,其占用空间大小为16字节,但是如果我们换一种声明方式,调整变量的顺序,重新运行程序,最后发现结构体test占用大小为12字节

struct test {     int a;     char b;     short d;     int c; }; 

空间存储情况如下,b和c存储在了一个字节快中:

0~3456~78~11ab填充内容cd

也就是说,如果我们在设计结构的时候,合理调整成员的位置,可以大大节省存储空间。

跨平台通信

由于不同平台对齐方式可能不同,如此一来,同样的结构在不同的平台其大小可能不同,在无意识的情况下,互相发送的数据可能出现错乱,甚至引发严重的问题。因此,为了不同处理器之间能够正确的处理消息,我们有两种可选的处理方法。

  • 1字节对齐
  • 自己对结构进行字节填充

我们可以使用伪指令#pragma pack(n)(n为字节对齐数)来使得结构间一字节对齐。
同样是前面的程序,如果在结构体test的前面加上伪指令,即如下:

#pragma pack(1) /*1字节对齐*/ struct test {     int a;     char b;     int c;     short d; }; #pragma pack()/*还原默认对齐*/ 

在这样的声明下,任何平台结构体test的大小都为11字节,这样做能够保证跨平台的结构大小一致,同时还节省了空间,但不幸的是,降低了效率。

当然了对于单个结构体,gcc还有如下的方法,使其1字节对齐

struct test {     int a;     char b;     int c;     short d; }__attribute__ ((packed)); 

注:

  • __attribute__((aligned (n))),让所作用的结构成员对齐在n字节自然边界上。如果结构中有成员的长度大于n,则按照最大成员的长度来对齐。
  • __attribute__ ((packed)),取消结构在编译过程中的优化对齐,也可以认为是1字节对齐。

除了前面的1字节对齐,还可以进行人为的填充,即test结构体声明如下:

struct test {     int a;     char b;     char reserve[3];     int c;     short d;     char reserve1[2]; }; 

访问效率高,但并不节省空间,同时扩展性不是很好,例如,当字节对齐有变化时,需要填充的字节数可能就会发生变化。

总结

虽然我们不需要具体关心字节对齐的细节,但是如果不关注字节对齐的问题,可能会在编程中遇到难以理解或解决的问题。因此针对字节对齐,总结了以下处理建议:

  • 结构体成员合理安排位置,以节省空间
  • 跨平台数据结构可考虑1字节对齐,节省空间但影响访问效率
  • 跨平台数据结构人为进行字节填充,提高访问效率但不节省空间
  • 本地数据采用默认对齐,以提高访问效率
posted @ 2020-01-09 16:54 长戟十三千 阅读(8) | 评论 (0)编辑 收藏
Linux 的虚拟内存管理有几个关键概念: 
1、每个进程都有独立的虚拟地址空间,进程访问的虚拟地址并不是真正的物理地址; 
2、虚拟地址可通过每个进程上的页表(在每个进程的内核虚拟地址空间)与物理地址进行映射,获得真正物理地址; 
3、如果虚拟地址对应物理地址不在物理内存中,则产生缺页中断,真正分配物理地址,同时更新进程的页表;如果此时物理内存已耗尽,则根据内存替换算法淘汰部分页面至物理磁盘中。 
   
基于以上认识,进行了如下分析:
一、Linux 虚拟地址空间如何分布?
Linux 使用虚拟地址空间,大大增加了进程的寻址空间,由低地址到高地址分别为: 
1、只读段:该部分空间只能读,不可写;(包括:代码段、rodata 段(C常量字符串和#define定义的常量) )
2、数据段:保存全局变量、静态变量的空间; 
3、堆 :就是平时所说的动态内存, malloc/new 大部分都来源于此。其中堆顶的位置可通过函数 brk 和 sbrk 进行动态调整。 
4、文件映射区域 :如动态库、共享内存等映射物理空间的内存,一般是 mmap 函数所分配的虚拟地址空间。 
5、栈:用于维护函数调用的上下文空间,一般为 8M ,可通过 ulimit –s 查看。 
6、内核虚拟空间:用户代码不可见的内存区域,由内核管理(页表就存放在内核虚拟空间)。
下图是 32 位系统典型的虚拟地址空间分布(来自《深入理解计算机系统》)。
32 位系统有4G 的地址空间::
      其中 0x08048000~0xbfffffff 是用户空间,0xc0000000~0xffffffff 是内核空间,包括内核代码和数据、与进程相关的数据结构(如页表、内核栈)等。另外,%esp 执行栈顶,往低地址方向变化;brk/sbrk 函数控制堆顶_edata往高地址方向变化。
64位系统结果怎样呢? 64 位系统是否拥有 2^64 的地址空间吗? 
事实上, 64 位系统的虚拟地址空间划分发生了改变: 
1、地址空间大小不是2^32,也不是2^64,而一般是2^48。因为并不需要 2^64 这么大的寻址空间,过大空间只会导致资源的浪费。64位Linux一般使用48位来表示虚拟地址空间,40位表示物理地址,
这可通过 /proc/cpuinfo 来查看 
address sizes   : 40 bits physical, 48 bits virtual 
2、其中,0x0000000000000000~0x00007fffffffffff 表示用户空间, 0xFFFF800000000000~ 0xFFFFFFFFFFFFFFFF 表示内核空间,共提供 256TB(2^48) 的寻址空间。
这两个区间的特点是,第 47 位与 48~63 位相同,若这些位为 0 表示用户空间,否则表示内核空间。 
3、用户空间由低地址到高地址仍然是只读段、数据段、堆、文件映射区域和栈;
 
二、malloc和free是如何分配和释放内存?
如何查看进程发生缺页中断的次数?
         用ps -o majflt,minflt -C program命令查看。
          majflt代表major fault,中文名叫大错误,minflt代表minor fault,中文名叫小错误。
          这两个数值表示一个进程自启动以来所发生的缺页中断的次数。
发成缺页中断后,执行了那些操作?
当一个进程发生缺页中断的时候,进程会陷入内核态,执行以下操作: 
1、检查要访问的虚拟地址是否合法 
2、查找/分配一个物理页 
3、填充物理页内容(读取磁盘,或者直接置0,或者啥也不干) 
4、建立映射关系(虚拟地址到物理地址) 
重新执行发生缺页中断的那条指令 
如果第3步,需要读取磁盘,那么这次缺页中断就是majflt,否则就是minflt。 
内存分配的原理
从操作系统角度来看,进程分配内存有两种方式,分别由两个系统调用完成:brk和mmap(不考虑共享内存)。
1、brk是将数据段(.data)的最高地址指针_edata往高地址推;
2、mmap是在进程的虚拟地址空间中(堆和栈中间,称为文件映射区域的地方)找一块空闲的虚拟内存。
     这两种方式分配的都是虚拟内存,没有分配物理内存。在第一次访问已分配的虚拟地址空间的时候,发生缺页中断,操作系统负责分配物理内存,然后建立虚拟内存和物理内存之间的映射关系。
在标准C库中,提供了malloc/free函数分配释放内存,这两个函数底层是由brk,mmap,munmap这些系统调用实现的。
下面以一个例子来说明内存分配的原理:
情况一、malloc小于128k的内存,使用brk分配内存,将_edata往高地址推(只分配虚拟空间,不对应物理内存(因此没有初始化),第一次读/写数据时,引起内核缺页中断,内核才分配对应的物理内存,然后虚拟地址空间建立映射关系),如下图:
1、进程启动的时候,其(虚拟)内存空间的初始布局如图1所示。
      其中,mmap内存映射文件是在堆和栈的中间(例如libc-2.2.93.so,其它数据文件等),为了简单起见,省略了内存映射文件。
      _edata指针(glibc里面定义)指向数据段的最高地址。 
2、进程调用A=malloc(30K)以后,内存空间如图2:
      malloc函数会调用brk系统调用,将_edata指针往高地址推30K,就完成虚拟内存分配。
      你可能会问:只要把_edata+30K就完成内存分配了?
      事实是这样的,_edata+30K只是完成虚拟地址的分配,A这块内存现在还是没有物理页与之对应的,等到进程第一次读写A这块内存的时候,发生缺页中断,这个时候,内核才分配A这块内存对应的物理页。也就是说,如果用malloc分配了A这块内容,然后从来不访问它,那么,A对应的物理页是不会被分配的。 
3、进程调用B=malloc(40K)以后,内存空间如图3。
情况二、malloc大于128k的内存,使用mmap分配内存,在堆和栈之间找一块空闲内存分配(对应独立内存,而且初始化为0),如下图:
4、进程调用C=malloc(200K)以后,内存空间如图4:
      默认情况下,malloc函数分配内存,如果请求内存大于128K(可由M_MMAP_THRESHOLD选项调节),那就不是去推_edata指针了,而是利用mmap系统调用,从堆和栈的中间分配一块虚拟内存。
      这样子做主要是因为::
      brk分配的内存需要等到高地址内存释放以后才能释放(例如,在B释放之前,A是不可能释放的,这就是内存碎片产生的原因,什么时候紧缩看下面),而mmap分配的内存可以单独释放。
      当然,还有其它的好处,也有坏处,再具体下去,有兴趣的同学可以去看glibc里面malloc的代码了。 
5、进程调用D=malloc(100K)以后,内存空间如图5;
6、进程调用free(C)以后,C对应的虚拟内存和物理内存一起释放。
7、进程调用free(B)以后,如图7所示:
        B对应的虚拟内存和物理内存都没有释放,因为只有一个_edata指针,如果往回推,那么D这块内存怎么办呢?
当然,B这块内存,是可以重用的,如果这个时候再来一个40K的请求,那么malloc很可能就把B这块内存返回回去了。 
8、进程调用free(D)以后,如图8所示:
        B和D连接起来,变成一块140K的空闲内存。
9、默认情况下:
       当最高地址空间的空闲内存超过128K(可由M_TRIM_THRESHOLD选项调节)时,执行内存紧缩操作(trim)。在上一个步骤free的时候,发现最高地址空闲内存超过128K,于是内存紧缩,变成图9所示。
三、既然堆内内存brk和sbrk不能直接释放,为什么不全部使用 mmap 来分配,munmap直接释放呢? 
        既然堆内碎片不能直接释放,导致疑似“内存泄露”问题,为什么 malloc 不全部使用 mmap 来实现呢(mmap分配的内存可以会通过 munmap 进行 free ,实现真正释放)?而是仅仅对于大于 128k 的大块内存才使用 mmap ? 
        其实,进程向 OS 申请和释放地址空间的接口 sbrk/mmap/munmap 都是系统调用,频繁调用系统调用都比较消耗系统资源的。并且, mmap 申请的内存被 munmap 后,重新申请会产生更多的缺页中断。例如使用 mmap 分配 1M 空间,第一次调用产生了大量缺页中断 (1M/4K 次 ) ,当munmap 后再次分配 1M 空间,会再次产生大量缺页中断。缺页中断是内核行为,会导致内核态CPU消耗较大。另外,如果使用 mmap 分配小内存,会导致地址空间的分片更多,内核的管理负担更大。
        同时堆是一个连续空间,并且堆内碎片由于没有归还 OS ,如果可重用碎片,再次访问该内存很可能不需产生任何系统调用和缺页中断,这将大大降低 CPU 的消耗。 因此, glibc 的 malloc 实现中,充分考虑了 sbrk 和 mmap 行为上的差异及优缺点,默认分配大块内存 (128k) 才使用 mmap 获得地址空间,也可通过 mallopt(M_MMAP_THRESHOLD, <SIZE>) 来修改这个临界值。
 
四、如何查看进程的缺页中断信息? 
可通过以下命令查看缺页中断信息 
ps -o majflt,minflt -C <program_name> 
ps -o majflt,minflt -p <pid> 
其中:: majflt 代表 major fault ,指大错误;
           minflt 代表 minor fault ,指小错误。
这两个数值表示一个进程自启动以来所发生的缺页中断的次数。
其中 majflt 与 minflt 的不同是::
        majflt 表示需要读写磁盘,可能是内存对应页面在磁盘中需要load 到物理内存中,也可能是此时物理内存不足,需要淘汰部分物理页面至磁盘中。
五、C语言的内存分配方式与malloc
  
C语言跟内存分配方式
(1) 从静态存储区域分配。内存在程序编译的时候就已经分配好,这块内存在程序的整个运行期间都存在。例如全局变量,static变量。
(2) 在栈上创建。在执行函数时,函数内局部变量的存储单元都可以在栈上创建,函数执行结束时这些存储单元自动被释放。栈内存分配运
算内置于处理器的指令集中,效率很高,但是分配的内存容量有限。
(3)从堆上分配,亦称动态内存分配。程序在运行的时候用malloc或new申请任意多少的内存,程序员自己负责在何时用free或delete释放内存。动态内存的生存期由我们决定,使用非常灵活,但问题也最多
     
      C语言跟内存申请相关的函数主要有 alloc,calloc,malloc,free,realloc,sbrk等.其中alloc是向栈申请内存,因此无需释放. malloc分配的内存是位于堆中的,并且没有初始化内存的内容,因此基本上malloc之后,调用函数memset来初始化这部分的内存空间.calloc则将初始化这部分的内存,设置为0. 而realloc则对malloc申请的内存进行大小的调整.申请的内存最终需要通过函数free来释放. 而sbrk则是增加数据段的大小;
       malloc/calloc/free基本上都是C函数库实现的,跟OS无关.C函数库内部通过一定的结构来保存当前有多少可用内存.如果程序 malloc的大小超出了库里所留存的空间,那么将首先调用brk系统调用来增加可用空间,然后再分配空间.free时,释放的内存并不立即返回给os, 而是保留在内部结构中. 可以打个比方: brk类似于批发,一次性的向OS申请大的内存,而malloc等函数则类似于零售,满足程序运行时的要求.这套机制类似于缓冲.
使用这套机制的原因: 系统调用不能支持任意大小的内存分配(有的系统调用只支持固定大小以及其倍数的内存申请,这样的话,对于小内存的分配会造成浪费; 系统调用申请内存代价昂贵,涉及到用户态和核心态的转换.
函数malloc()和calloc()都可以用来分配动态内存空间,但两者稍有区别。
      在Linux系统上,程序被载入内存时,内核为用户进程地址空间建立了代码段、数据段和堆栈段,在数据段与堆栈段之间的空闲区域用于动态内存分配。
      内核数据结构mm_struct中的成员变量start_code和end_code是进程代码段的起始和终止地址,start_data和 end_data是进程数据段的起始和终止地址,start_stack是进程堆栈段起始地址,start_brk是进程动态内存分配起始地址(堆的起始 地址),还有一个 brk(堆的当前最后地址),就是动态内存分配当前的终止地址。
C语言的动态内存分配基本函数是malloc(),在Linux上的基本实现是通过内核的brk系统调用。brk()是一个非常简单的系统调用,只是简单地改变mm_struct结构的成员变量brk的值。
      mmap系统调用实现了更有用的动态内存分配功能,可以将一个磁盘文件的全部或部分内容映射到用户空间中,进程读写文件的操作变成了读写内存的操作。在 linux/mm/mmap.c文件的do_mmap_pgoff()函数,是mmap系统调用实现的核心。do_mmap_pgoff()的代码,只是新建了一个vm_area_struct结构,并把file结构的参数赋值给其成员变量m_file,并没有把文件内容实际装入内存。
Linux内存管理的基本思想之一,是只有在真正访问一个地址的时候才建立这个地址的物理映射。
————————————————
版权声明:本文为CSDN博主「gfgdsg」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/gfgdsg/article/details/42709943
posted @ 2019-12-25 15:36 长戟十三千 阅读(4) | 评论 (0)编辑 收藏
     摘要: brk() , sbrk() 的声明如下:#include <unistd.h>int brk(void *addr);void *sbrk(intptr_t increment);这两个函数都用来改变 "program break" (程序间断点)的位置,这个位置可参考下图:如 man 里说的:引用brk()  and  sbrk() chan...  阅读全文
posted @ 2019-12-25 15:25 长戟十三千 阅读(5) | 评论 (0)编辑 收藏

在windows平台,有一个简单的方法来追踪调用函数的堆栈,就是利用函数CaptureStackBackTrace,但是这个函数不能得到具体调用函数的名称,只能得到地址,当然我们可以通过反汇编的方式通过地址得到函数的名称,以及具体调用的反汇编代码,但是对于有的时候我们需要直接得到函数的名称,这个时候据不能使用这个方法,对于这种需求我们可以使用函数:SymInitialize、StackWalk、SymGetSymFromAddr、SymGetLineFromAddr、SymCleanup。

原理

基本上所有高级语言都有专门为函数准备的堆栈,用来存储函数中定义的变量,在C/C++中在调用函数之前会保存当前函数的相关环境,在调用函数时首先进行参数压栈,然后call指令将当前eip的值压入堆栈中,然后调用函数,函数首先会将自身堆栈的栈底地址保存在ebp中,然后抬高esp并初始化本身的堆栈,通过多次调用最终在堆栈段形成这样的布局

这里对函数的原理做简单的介绍,有兴趣的可以看我的另一篇关于C函数原理讲解的博客,点击这里跳转 VC++编译器在编译时对函数名称与地址都有详细的记录,编译出来的程序都有一个符号常量表,将符号常量与它对应的地址形成映射,在搜索时首先根据这些堆栈环境找到对应地址,然后根据地址在符号常量表中,找到具体调用的信息,这是一个很复杂的工程,需要对编译原理和汇编有很强的基础,幸运的是,如今这些工作不需要程序员自己去做,windows帮助我们分配了一组API,在编写程序时只需要调用API即可

函数说明

SymInitialize:这个函数主要用作初始化相关环境。 SymCleanup:清楚这个初始化的相关环境,在调用SymInitialize之后需要调用SymCleanup,进行释放资源的操作 StackWalk:程序的功能主要由这个函数实现,函数会从初始化时的堆栈顶开始向下查找下一个堆栈的信息,原型如下:

BOOL WINAPI StackWalk(   __in          DWORD MachineType, //机器类型现在一般是intel的x86系列,这个时候填入IMAGE_FILE_MACHINE_I386   __in          HANDLE hProcess, //追踪的进程句柄   __in          HANDLE hThread, //追踪的线程句柄   __in_out      LPSTACKFRAME StackFrame, //记录的追踪到的堆栈信息   __in_out      PVOID ContextRecord, //记录当前的线程环境   __in          PREAD_PROCESS_MEMORY_ROUTINE ReadMemoryRoutine,   __in          PFUNCTION_TABLE_ACCESS_ROUTINE FunctionTableAccessRoutine,   __in          PGET_MODULE_BASE_ROUTINE GetModuleBaseRoutine,   __in          PTRANSLATE_ADDRESS_ROUTINE TranslateAddress //后面的四个参数都是回掉函数,有系统自行调用,而且这些函数都是定义好的,只需要填入相应的函数名称 );

需要注意的一点是,在首次调用该函数时需要对StackFrame中的AddrPC、AddrFrame、AddrStack这三个成员进行初始化,填入相关值,以便函数从此处线程堆栈的栈顶进行搜索,否则调用函数将失败,具体如何填写请看MSDN。

SymGetSymFromAddr:根据获取到的函数地址得到函数名称、堆栈大小等信息,这个函数的原型如下: BOOL WINAPI SymGetSymFromAddr(   __in          HANDLE hProcess, //进程句柄   __in          DWORD Address, //函数地址   __out         PDWORD Displacement, //返回该符号常量的位移或者填入NULL,不获取此值   __out         PIMAGEHLP_SYMBOL Symbol//返回堆栈信息 );

SymGetLineFromAddr:根据得到的地址值,获取调用函数的相关信息。主要记录是在哪个文件,哪行调用了该函数,下面是函数原型:

BOOL WINAPI SymGetLineFromAddr(   __in          HANDLE hProcess,   __in          DWORD dwAddr,   __out         PDWORD pdwDisplacement,   __out         PIMAGEHLP_LINE Line );

它参数的含义与SymGetSymFromAddr,相同。 通过上面对函数的说明,我们可以知道,为了追踪函数调用的详细信息,大致步骤如下: 1. 首先调用函数SymInitialize进行相关的初始化工作。 2. 填充结构体StackFrame的相关信息,确定从何处开始追踪。 3. 循环调用StackWalk函数,从指定位置,向下一直追踪到最后。 4. 每次将获取的地址分别传入SymGetSymFromAddr、SymGetLineFromAddr,得到函数的详细信息 5. 调用SymCleanup,结束追踪 但是需要注意的一点是,函数StackWalk会顺着线程堆栈进行查找,如果在调用之前,某个函数已经返回了,它的堆栈被回收,那么函数StackWalk自然不会追踪到该函数的调用。

具体实现

void InitTrack() {     g_hHandle = GetCurrentProcess();      SymInitialize(g_hHandle, NULL, TRUE); }  void StackTrack() {     g_hThread = GetCurrentThread();     STACKFRAME sf = { 0 };      sf.AddrPC.Offset = g_context.Eip;     sf.AddrPC.Mode = AddrModeFlat;      sf.AddrFrame.Offset = g_context.Ebp;     sf.AddrFrame.Mode = AddrModeFlat;      sf.AddrStack.Offset = g_context.Esp;     sf.AddrStack.Mode = AddrModeFlat;      typedef struct tag_SYMBOL_INFO     {         IMAGEHLP_SYMBOL symInfo;         TCHAR szBuffer[MAX_PATH];     } SYMBOL_INFO, *LPSYMBOL_INFO;      DWORD dwDisplament = 0;     SYMBOL_INFO stack_info = { 0 };     PIMAGEHLP_SYMBOL pSym = (PIMAGEHLP_SYMBOL)&stack_info;     pSym->SizeOfStruct = sizeof(IMAGEHLP_SYMBOL);     pSym->MaxNameLength = sizeof(SYMBOL_INFO) - offsetof(SYMBOL_INFO, symInfo.Name);     IMAGEHLP_LINE ImageLine = { 0 };     ImageLine.SizeOfStruct = sizeof(IMAGEHLP_LINE);      while (StackWalk(IMAGE_FILE_MACHINE_I386, g_hHandle, g_hThread, &sf, &g_context, NULL, SymFunctionTableAccess, SymGetModuleBase, NULL))     {         SymGetSymFromAddr(g_hHandle, sf.AddrPC.Offset, &dwDisplament, pSym);         SymGetLineFromAddr(g_hHandle, sf.AddrPC.Offset, &dwDisplament, &ImageLine);         printf("当前调用函数 : %08x+%s(FILE[%s]LINE[%d])\n", pSym->Address, pSym->Name, ImageLine.FileName, ImageLine.LineNumber);     }  }  void UninitTrack() {     SymCleanup(g_hHandle); }

测试程序如下:

void func1() {     OPEN_STACK_TRACK; }  void func2() {     func1(); }  void func3() {     func2();  } void func4() {     printf("hello\n"); }  int _tmain(int argc, TCHAR* argv[]) {     func4();     func3();     func3();     return 0; }

OPEN_STACK_TRACK是一个宏,它的定义如下:

#define OPEN_STACK_TRACK\  HANDLE hThread = GetCurrentThread();\ GetThreadContext(hThread, &g_context);\ __asm{call $ + 5}\ __asm{pop eax}\ __asm{mov g_context.Eip, eax}\ __asm{mov g_context.Ebp, ebp}\ __asm{mov g_context.Esp, esp}\ InitTrack();\ StackTrack();\ UninitTrack();

这个程序需要注意以下几点: 1. 如果想要追踪所有调用的函数,需要将这个宏放置到最后调用的位置,当然前提是此时之前被调函数的堆栈仍然存在。当然可以在调用前简单的计算,找出在哪个位置是所有函数都没有调用完成的,不过这样可能就与程序的初衷相悖,毕竟程序本身就是为了获取堆栈的调用信息。。。。 2. IMAGEHLP_SYMBOL的结构体中关于Name的成员,只有一个字节,而函数SymGetSymFromAddr在填入值时是没有关心这个实际大小,它只是简单的填充,这就造成了缓冲区溢出的情况,为了避免我们需要在Name后面额外给一定大小的缓冲区,用来接收数据,这也就是我们定义这个结构体SYMBOL_INFO的原因。另外IMAGEHLP_SYMBOL中的MaxNameLength成员是指Name的最大长度,需要根据给定的缓冲区,进行计算。 3. 从测试程序来看,在进行追踪时func4已经调用完成,而我们在获取线程的运行时环境g_context时函数GetThreadContext,也在堆栈中,最终得到的结果中必然包含GetThreadContext的调用信息,如果想去掉这个信息,只需要修改获得信息的值,既然函数StackWalk是根据堆栈进行追踪,那么只需要修改对应堆栈的信息即可,需要修改eip 、ebp、esp的值,关于esp ebp的值很好修改,可以在对应函数中esp ebp这些寄存器的值,而eip的值就不那么好获取,本生利用mov指令得到eip的值它也是指令,会改变eip的值,从而造成获取到的eip的值不准确,所以我们利用call指令,先保存当前eip的值到堆栈,然后再从堆栈中取出。call指令的实质是 push eip和jmp addr指令的组合,并不一定非要调用函数。call指令的大小为5个字节,所以call $ + 5表示先保存eip在跳转到它的下一跳指令处。这样就可以有效的避免检测到GetThreadContext中的相关函数调用

posted @ 2019-12-19 12:39 长戟十三千 阅读(4) | 评论 (0)编辑 收藏
     摘要: 文档名称:Windows NT Stack Trace文档维护:welfear创建时间:2009年6月7日更新内容:对StackWalk的分析(2009.6.17)更新内容:对x64栈的分析(2009.6.19) 在系统软件开发中有时会有得到函数调用者的信息的需要,为此WindowsNT专门提供了调用RtlGetCallerAddress为内核开发者使用,但它并没有公开所以也就不能为驱动...  阅读全文
posted @ 2019-12-19 12:34 长戟十三千 阅读(7) | 评论 (0)编辑 收藏

取模
最简单的hash算法

targetServer = serverList[hash(key) % serverList.size]

直接用key的hash值(计算key的hash值的方法可以自由选择,比如算法CRC32、MD5,甚至本地hash系统,如Java的hashcode)模上server总数来定位目标server。这种算法不仅简单,而且具有不错的随机分布特性。

但是问题也很明显,server总数不能轻易变化。因为如果增加/减少memcached server的数量,对原先存储的所有key的后续查询都将定位到别的server上,导致所有的cache都不能被命中而失效。

一致性hash
为了解决这个问题,需要采用一致性hash算法(consistent hash)
相对于取模的算法,一致性hash算法除了计算key的hash值外,还会计算每个server对应的hash值,然后将这些hash值映射到一个有限的值域上(比如0~2^32)。通过寻找hash值大于hash(key)的最小server作为存储该key数据的目标server。如果找不到,则直接把具有最小hash值的server作为目标server。

为了方便理解,可以把这个有限值域理解成一个环,值顺时针递增。
circle space
如上图所示,集群中一共有5个memcached server,已通过server的hash值分布到环中。

如果现在有一个写入cache的请求,首先计算x=hash(key),映射到环中,然后从x顺时针查找,把找到的第一个server作为目标server来存储cache,如果超过了2^32仍然找不到,则命中第一个server。比如x的值介于A~B之间,那么命中的server节点应该是B节点
image
可以看到,通过这种算法,对于同一个key,存储和后续的查询都会定位到同一个memcached server上。

那么它是怎么解决增/删server导致的cache不能命中的问题呢?
假设,现在增加一个server F,如下图


此时,cache不能命中的问题仍然存在,但是只存在于B~F之间的位置(由C变成了F),其他位置(包括F~C)的cache的命中不受影响(删除server的情况类似)。尽管仍然有cache不能命中的存在,但是相对于取模的方式已经大幅减少了不能命中的cache数量。

虚拟节点
但是,这种算法相对于取模方式也有一个缺陷:当server数量很少时,很可能他们在环中的分布不是特别均匀,进而导致cache不能均匀分布到所有的server上。

posted @ 2019-12-18 15:42 长戟十三千 阅读(13) | 评论 (0)编辑 收藏
仅列出标题  下一页